# Theory of Computing Seminar

Friday
February 13, 2015
12:00 PM

**Breaking the Minsky-Papert Barrier for Constant-Depth Circuits **

**Speaker:**Alexander Sherstov, UCLA

**Location:**Annenberg 107

**Abstract:**

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).

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).

**Series**Theory of Computing Seminar Series

**Contact:** Thomas Vidick vidick@cms.caltech.edu