Abstract: Representations of Boolean functions by polynomials play a vital role in theoretical computer science. The idea of representing a Boolean function by the sign of a polynomial has been particularly fruitful. Formally, the threshold degree of f is the minimum degree of a real polynomial p with f(x) = sgn p(x) for all x.
I will discuss the classic, unresolved problem of determining the maximum threshold degree of a polynomial-size constant-depth circuit in n variables (Minsky and Papert, 1969). Work on this question over the decades has led to some of the strongest algorithmic and complexity-theoretic results for constant-depth circuits. The best lower bound prior to our work was Ω(n(d-1)/(2d-1)) for depth d. We obtain a polynomial improvement for every depth d, with a lower bound of Ω(n3/7) for depth 3 and Ω(√n) for depth d ≥ 4. The proof crucially exploits the power of asymmetry in constant-depth circuits, in contrast to the longstanding focus on symmetric constructions.
Speaker Bio: Alexander Sherstov is a professor of computer science at the University of California, Los Angeles. He has broad research interests in theoretical computer science, including computational complexity theory, computational learning, and quantum computing. Sherstov is a recent recipient of an NSF CAREER award (2012), a Sloan Research Fellowship (2014), a Northrop Grumman Excellence in Teaching Award (2014), and a Samueli Fellowship (2015).