Analytic Methods in Concrete Complexity.
详细信息
文摘
This thesis studies computational complexity in concrete models of computation. We draw on a range of mathematical tools to understand the structure of Boolean functions,with analytic methods---Fourier analysis,probability theory,and approximation theory---playing a central role. These structural theorems are leveraged to obtain new computational results,both algorithmic upper bounds and complexity-theoretic lower bounds,in property testing,learning theory,and circuit complexity. We establish the best-known upper and lower bounds on the classical problem of testing whether an unknown Boolean function is monotone. We prove an On1/5) lower bound on the query complexity of non-adaptive testers,an exponential improvement over the previous lower bound of Olog n) from 2002. We complement this with an On5/6)-query non-adaptive algorithm for the problem. We characterize the statistical query complexity of agnostically learning Boolean functions with respect to product distributions. We show that l1-approximability by low-degree polynomials,known to be sufficient for efficient learning in this setting,is in fact necessary. As an application we establish an optimal lower bound showing that no statistical query algorithm can efficiently agnostically learn monotone k-juntas for any k ＝ o1) and any constant error less than 1/2. We initiate a systematic study of the tradeoffs between accuracy and efficiency in Boolean circuit complexity,focusing on disjunctive normal form formulas,among the most basic types of circuits. A conceptual message that emerges is that the landscape of circuit complexity changes dramatically,both qualitatively and quantitatively,when the formula is only required to approximate a function rather than compute it exactly. Finally we consider the Fourier Entropy-Influence Conjecture,a longstanding open problem in the analysis of Boolean functions with significant applications in learning theory,the theory of pseudorandomness,and random graph theory. We prove a composition theorem for the conjecture,broadly expanding the class of functions for which the conjecture is known to be true.