Formulas versus Circuits for Small Distance Connectivity
Benjamin Rossman · SIAM Journal on Computing · 2018
We prove an $n^{\Omega(\log k)}$ lower bound on the $\mathsf{AC^0}$ formula size of Distance $k(n)$ Connectivity for all $k(n) \le \log\log n$ and formulas up to depth $\log n/(\log\log n)^{O(1)}$. This lower bound strongly separates the power of bounded-depth formulas versus circuits, since Distance $k(n)$ Connectivity is solvable by polynomial-size $\mathsf{AC^0}$ circuits of depth $O(\log k)$. For all $d(n) \le \log\log\log n$, it follows that polynomial-size depth-$d$ circuits---which are a semantic subclass of $n^{O(d)}$-size depth-$d$ formulas---are not a semantic subclass of $n^{o(d)}$-size formulas of much higher depth $\log n/(\log\log n)^{O(1)}$. Our lower bound technique probabilistically associates each gate in an $\mathsf{AC^0}$ formula with an object called a pathset. We show that with high probability these random pathsets satisfy a family of density constraints called smallness, a property akin to low average sensitivity. We then study a complexity measure on small pathsets, which lower bounds the $\mathsf{AC^0}$ formula size of Distance $k(n)$ Connectivity. The heart of our technique is an $n^{\Omega(\log k)}$ lower bound on this pathset complexity measure.