### The Power of Asymmetry in Constant-Depth Circuits

**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 Ω(n^{3/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).