TR14-009 Authors: Alexander A. Sherstov

Publication: 21st January 2014 08:46

Downloads: 4538

Keywords:

The threshold degree of a Boolean function $f$ is the minimum degree of

a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969

monograph, Minsky and Papert constructed a polynomial-size constant-depth

$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ This bound underlies

some of today's strongest results on 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 fixed $k\geq1,$ we construct

an $\{\wedge,\vee\}$-formula of size $n$ and depth $k$ with threshold degree $\Omega(n^{\frac{k-1}{2k-1}})$. This lower

bound nearly matches a known $O(\sqrt{n})$ bound for arbitrary formulas, and is exactly

tight for regular formulas. Our result proves a conjecture due to O'Donnell and

Servedio (STOC 2003) and a different conjecture due to Bun and Thaler (2013).

Applications to communication complexity and computational learning are given.