skip to main content

Theory of Computing Seminar

Friday, February 13, 2015
12:00pm to 1:00pm
Add to Cal
Annenberg 107
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits
Alexander Sherstov, UCLA,


The threshold degree of a Boolean function f is the minimum
degree of a real polynomial p that represents f in sign:
f(x)=sgn p(x).  In a seminal 1969 monograph, Minsky and Papert
constructed a polynomial-size constant-depth AND/OR circuit
in n variables with threshold degree Omega(n^{1/3}). This bound
underlies the fastest known algorithms for constant-depth
circuits. It has been an open problem (O'Donnell and Servedio,
STOC 2003) to improve Minsky and Papert's bound to n^{Omega(1)+1/3}.

We give a detailed solution to this problem. For any k>=1, we
construct an AND/OR formula of size n and depth k with threshold
degree Omega(n^{(k-1)/(2k-1)}).  This lower bound nearly matches
the famous O(sqrt(n)) bound for arbitrary formulas (Ambainis,
Childs, Reichardt, Spalek, Zhang, FOCS 2007).  Our result
proves a conjecture due to O'Donnell and Servedio (STOC 2003)
and a different conjecture due to Bun and Thaler (2013). 
For more information, please contact Thomas Vidick by email at [email protected].