Rocco Servedio: Two Circuit Lower Bounds

Abstract:

We present two recent lower bounds on small-depth circuits.

The first lower bound deals with shallow monotone circuits of Majority gates (unweighted threshold gates).  We show that for any d, a monotone depth-d circuit of Majority gates needs size 2^{n^{1/d}} to compute a particular explicit (monotone) weighted n-variable threshold function.  This answers questions of Goldmann and Karpinski (1993) and Hastad (2010, 2014), and can be viewed as a step towards showing that monotone TC0 is not contained in monotone NC1.

The second lower bound gives a near-optimal size-depth tradeoff for circuits computing the “distance-k connectivity function” on graphs.  Our lower bound here extends results of Beame, Impagliazzo and Pitassi (1993) and Rossman (2014) and may be viewed as giving evidence towards the optimality of Savitch’s small-space algorithm for directed s-t connectivity.  This lower bound is proved via “random projections”, an extension of the classic technique of random restrictions that has recently proved useful in other contexts in circuit complexity.

Joint work with Xi Chen, Igor Oliveira, and Li-Yang Tan.