This dissertation presents some circuit complexity results and techniques. Circuit complexity is a branch of computational complexity dealing with classes of circuit families as opposed to classes of Turing Machines. Recent research has shown that there are rich connections between circuit complexity and other areas in theoretical computer science: Carmosino et al. construct learning algorithms from "natural" circuit lower bounds; Murray and Williams show that slightly better than brute-force SAT algorithms lead to circuit lower bounds against NP, and; Ilango, Ren, and Santhanam show that the existence of one-way functions is equivalent to hard distributions with certain properties existing for the Minimum Circuit Size Problem (MCSP). A common theme throughout these results is the concept of "meta-algorithms," algorithms which take functions as input and attempt to either construct objects computing the function in some way (e.g. construct a circuit that well-approximates the function), or finding some computationally relevant quantity (e.g. what is the minimum size of a circuit computing the function).
This dissertation will focus on circuit complexity and MCSP for classes of low-depth circuits, particularly those of bounded fan-in. Here, we will present a lifting theorem from small-constant-depth bounded bottom fan-in circuits to larger-constant-depth bounded bottom fan-in circuits, leading to a reduction between MCSP for the corresponding classes. As part of this, we also present a new switching lemma, which may be of independent interest. We then demonstrate that MCSP for depth-2 bounded bottom fan-in circuits is NP-hard to compute, and is approximable within a factor of O(log N). After, we give a barrier result stating that "natural" reductions between MCSP for different fixed-depth circuit classes yields unexpectedly fast MCSP algorithms or new circuit lower bounds against these classes. Finally, we introduce a family of new models of communication complexity and give some upper and lower bounds in these models, with an eye to separating P from fan-in 2 O(log n)-depth circuits.
Bole is a Chadic language spoken in Yobe and Gombe States in northeastern Nigeria. The Bole tone system has two contrasting level tones, high (H) and low (L), which may be combined on heavy syllables to produce phonetic rising and falling tones. The prosody of intonation refers to lexical tones and the overall function of the utterance. Bole does not have lexical or phrasal stress, and intonation does not play a pragmatic role typical of stress languages, such as pitch raising to signal focus. The paper discusses intonation patterns of several phrasal types: declarative statements, yes/no questions of two types, WHquestions, vocatives, pleas, and lists. Certain interactions of intonation with tone apply to most of these phrase types: downdrift (esp. of H following L) across a phrase, phrase final tone lowering (extra lowering of phrase final L and plateauing of phrase final H after L), and boosting of H in the first HL sequence of a phrase. Special phrase final pitch phenomena in yes/no questions and pleas are described as appending extra-high (XH) and HL tones espectively. The last section discusses XH associated with ideophonic words, arguing that such words have lexical H tone which is intonationally altered to XH phrase finally.
Cookie SettingseScholarship uses cookies to ensure you have the best experience on our website. You can manage which cookies you want us to use.Our Privacy Statement includes more details on the cookies we use and how we protect your privacy.
