The complexity of meta-computational problems

This thesis focuses on problems which themselves encode questions about circuits or algorithms, also called meta-computational problems. The thesis is centered on meta-computational problems like C-MCSP (minimum circuit size problem), C-Learnability and C-Satisfiability, for some circuit class C. We study mathematical questions pertaining to such problems, and their deep connections to the theory of lower bounds, which is a general theme that has attracted a lot of interest in recent years among complexity theorists. We first study non-uniform lower bounds for MCSP (and its variants) motivated by its importance for the theory of Hardness Magnification. Thisphenomenon reduces major complexity separations (such as NP is not in NC^1) to proving “barely” non-trivial lower bounds for natural problems like MCSP against weak circuit classes. In most interesting cases, we already have such required lower bounds, but for a different, seemingly easier problem. Firstly, we establish that instantiations of magnification for certain variants of MCSP provably refute the existence of natural proofs against P/poly, which indicates that the natural proofs barrier by Razborov-Rudich may not be relevant to this approach. This is done by establishing a connection from hardness magnification to hardness of efficiently learning polynomial-sized circuits. Next, we investigate the future prospects of proving new lower bounds using magnification. We identify a new source of difficulty called the locality barrier, when trying to adapt existing lower bound techniques to prove strong separations via magnification. We show that this barrier applies to many current instantiations of hardness magnification, that involve a wide range of restricted computational models. Next we consider learnability, and initiate a top-down study of hardness of learning circuit classes, i.e. we consider hardness of learning circuit classes more powerful than P/poly. Our goal is to understand the power and limitations of current complexity theoretic techniques in showing unconditional results for learning. We show unconditional hardness results for efficiently learning classes like BPE/poly, EXP/poly and PSPACE/poly on one hand, and on the other, show that it is implausible that one can extend these ideas to prove the NP-Hardness of learning classes like non-deterministic polynomial-sized circuits, i.e. NP/poly. Finally, we consider the algorithmic question of counting the number of satisfying assignments of an input AC^0[2]-circuit. We construct a deterministic #SAT-algorithm for AC^0[2] circuits of depth d and size 2^(O(n^(1/d))), which beats brute-force running time non-trivially. The algorithm is designed using the Razborov-Smolensky polynomial method, whose original motivation was to prove AC^0[2] lower bounds. We then show a lower bound for E^NP against AC^0[2]-circuits of size 2^(Ω(n^(1/d+1))), which was the best known lower bound against this class until very recently.