Formulas vs. circuits for small distance connectivity
Benjamin Rossman · 2014
We give the first super-polynomial separation in the power of bounded-depth boolean formulas vs. circuits. Specifically, we consider the problem Distance k(n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a path of length at most k(n). This problem is solvable (by the recursive doubling technique) on circuits of depth O(log k) and size O(kn3). In contrast, we show that solving this problem on formulas of depth log n/(log log n)O(1) requires size nΩ(log k) for all k(n) ≤ log log n. As corollaries: