Li-Yang Tan: An average-case depth hierarchy theorem for Boolean circuits + Circuit complexity of small distance connectivity

Practicalities

Lunch is served at 12:00 noon (register at  this doodle at the latest the Saturday before, but preferably earlier ). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for ca two hours of more technical discussions.

ABSTRACT

In the first hour I will speak about recent work with Ben Rossman and Rocco Servedio. We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d >= 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d-1) circuit that agrees with f on \((1/2 + o_n(1))\) fraction of all inputs must have size \(\exp(n^{\Omega(1/d)})\). This answers an open question posed by Håstad in his Ph.D. thesis, and has applications in structural complexity and the analysis of Boolean functions. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

After the break, I'd be happy to present the technical details and/or speak about related subsequent work with Xi Chen, Igor Oliveira, and Rocco Servedio on the st-connectivity problem:

We show that any depth-d circuit for determining whether an n-node graph has an s-to-t path of length at most k must have size \(n^{\Omega(k^{1/d}/d)}\). The previous best circuit size lower bounds for this problem were \(n^{k^{\exp(-O(d))}}\) [Beame, Impagliazzo, Pitassi 1998] and n^{\Omega((\log k)/d)} [Rossman 2014]. Our lower bound is quite close to optimal, since a simple construction gives depth-d circuits of size \(n^{O(k^{2/d})}\) for this problem. Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the "Sipser functions" that have played an important role in classical circuit lower bounds of Sipser, Yao, and Håstad. A key ingredient in our proof is the use of random projections, an extension of random restrictions which allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works.