UC San Diego

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.