"The Power of Asymmetry in Constant-Depth Circuits"
Alexander Sherstov
(UCLA)
Thursday, May 28th, 2015, 2:00 pm
EBU3B, Room 4258
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). Introduced in the seminal work of Minsky and Papert (1969), this notion is crucial to some of the strongest algorithmic and complexity-theoretic results obtained to date for constant-depth circuits (AC0). A basic unsolved problem, with applications to computational learning and communication complexity, is to determine the maximum threshold degree of an AC0 circuit. For 35 years the strongest bound remained Minsky and Papert's Omega(n^{1/3}), improved to Omega(n^{1/3} log^(d-2) n) for depth d>1 by O'Donnell and Servedio (STOC 2003), and more recently to Omega(n^{(d-1)/(2d-1)}) for depth d (Sherstov, STOC 2013).
We obtain a polynomially stronger lower bound of Omega(sqrt(n)) for an explicitly given constant-depth circuit, solving an open problem due to Bun and Thaler (2013). The proof introduces a novel approximation-theoretic technique of independent interest, which relies on asymmetry in circuits to prove their hardness for polynomials. In contrast, previous analyses worked exclusively with symmetric constructions.