We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let @math be a Boolean function and consider a function @math obtained by applying @math to conjunctions of possibly overlapping subsets of @math variables. If @math has quantum query complexity @math , we give an algorithm for evaluating @math using @math quantum queries. This improves on the bound of @math that follows by treating each conjunction independently, and is tight for worst-case choices of @math . Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of @math . By recursively applying our composition theorems, we obtain a nearly optimal @math upper bound on the quantum query complexity and approximate degree of linear-size depth- @math AC @math circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC @math circuits. We also show that any substantially faster learning algorithm will require fundamentally new techniques.
Even in the relatively easier PAC model, only a small number of circuit classes are known to be learnable in subexponential time. For the well-studied class of polynomial-size DNFs, or depth-2 circuits, we have an algorithm running in time @math @cite_7 , and we know that new techniques will be needed to improve this bound @cite_2 . Little is known about larger subclasses of , other than a recent paper that studied depth-3 circuits with top fan-in @math , giving a PAC learning algorithm of runtime @math @cite_8 , which is only subexponential when @math .
@cite_8 @cite_7 @cite_2
1517311456 2117822564
Using techniques from learning theory, we show that any s-term DNF over n variables can be computed by a polynomial threshold function of degree O(n1 3 log s). This upper bound matches, up to a logarithmic factor, the longstanding lower bound given by Minsky and Papert in their 1968 book Perceptrons. As a consequence of this upper bound we obtain the fastest known algorithm for learning polynomial size DNF, one of the central problems in computational learning theory. The sign-rank of a matrix @math with @math entries is the least rank of a real matrix @math with @math for all @math . We obtain the first exponential lower bound on the sign-rank of a function in @math . Namely, let @math . We show that the matrix @math has sign-rank @math . This in particular implies that @math , which solves a longstanding open problem in communication complexity posed by Babai, Frankl, and Simon [Proceedings of the 27th Symposium on Foundations of Computer Science (FOCS), 1986, pp. 337-347]. Our result additionally implies a lower bound in learning theory. Specifically, let @math be functions such that every DNF formula @math of polynomial size has the representation @math for some reals @math . We prove that then @math , which essentially matches an upper bound of @math , due to Klivans and Servedio [J. Comput. System Sci., 68 (2004), pp. 303-318]. Finally, our work yields the first exponential lower bound on the size of threshold-of-majority circuits computing a function in @math . This substantially generalizes and strengthens the results of Krause and Pudlak [Theoret. Comput. Sci., 174 (1997), pp. 137-156].