Near-optimal small-depth lower bounds for small distance connectivity.
X. Chen and I. Oliveira and R. Servedio and L.-Y. Tan.
In 48th Annual Symposium on Foundations of Computer Science (STOC), 2016, pp. 612-625.


Abstract: We show that any depth-d circuit for determining whether an n-vertex 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))}} (due to Beame, Impagliazzo, and Pitassi, 1993) and n^{\Omega((\log k)/d)} (following from a 2013 formula size lower bound of Rossman). Our lower bound is quite close to optimal, as a simple construction gives depth-d circuits of size n^{O(k^{2/d})} for this problem (and strengthening our bound even to n^{k^{\Omega(1/d)}} would require proving that undirected connectivity is not in NC^1).

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 (Sipser 1983, Yao 1985, Hastad 1986). A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of random projections, an extension of random restrictions which were recently employed in work of Rossman, Servedio and Tan (2015). Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works (Ajtai 1989, Beame, Pitassim Urquhart 1992, Beame, Impagliazzo, Pitassi 1998, Rossman 2013).

Link to full version on ArXiV


Back to main papers page