BREAKING THE MINSKY-PAPERT BARRIER FOR CONSTANT-DEPTH CIRCUITS

摘要

The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign f (x) sign. In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth {boolean AND, boolean OR}-circuit in n variables with threshold degree Omega(n(1/3)). This lower bound underlies some of today's strongest results on constant-depth circuits. It has since been an open problem [R. O'Donnell and R. A. Servedio: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 325-334] to improve Minsky and Papert's bound to n(Omega(1)+1/3). We give a detailed solution to this problem. For any fixed k = 1, we construct an {boolean AND, boolean OR}-formula of size n and depth k with threshold degree Omega(n((k-1)/(2k-1))). This lower bound nearly matches a known O(root n) upper bound for arbitrary formulas and is exactly tight for "regular" formulas. Our result proves a conjecture due to O'Donnell and Servedio and a different conjecture due to [M. Bun and J. Thaler: Electronic Colloquium on Computational Complexity, Report TR13-151, 2013]. Applications to communication complexity and computational learning are given.