ECCC-Report TR13-169https://eccc.weizmann.ac.il/report/2013/169Comments and Revisions published for TR13-169en-usMon, 02 Dec 2013 08:24:48 +0200
Paper TR13-169
| Formulas vs. Circuits for Small Distance Connectivity |
Benjamin Rossman
https://eccc.weizmann.ac.il/report/2013/169We 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(kn^3)$. In contrast, we show that solving this problem on formulas of depth $\log n/(\log\log n)^{O(1)}$ requires size $n^{\Omega(\log k)}$ for all $k(n) \leq \log\log n$. As corollaries:
(i) It follows that polynomial-size circuits for Distance $k(n)$ Connectivity require depth $\Omega(\log k)$ for all $k(n) \leq \log\log n$. This matches the upper bound from recursive doubling and improves a previous $\Omega(\log\log k)$ lower bound of Beame, Pitassi and Impagliazzo [BIP98].
(ii) We get a tight lower bound of $s^{\Omega(d)}$ on the size required to simulate size-$s$ depth-$d$ circuits by depth-$d$ formulas for all $s(n) = n^{O(1)}$ and $d(n) \leq \log\log\log n$. No lower bound better than $s^{\Omega(1)}$ was previously known for any super-constant $d(n)$.
Our proof technique is centered on a new notion of pathset complexity, which roughly speaking measures the minimum cost of constructing a set of (partial) paths in a universe of size $n$ via the operations of union and relational join, subject to certain density constraints. Half of our proof shows that bounded-depth formulas solving Distance $k(n)$ Connectivity imply upper bounds on pathset complexity. The other half is a combinatorial lower bound on pathset complexity.Mon, 02 Dec 2013 08:24:48 +0200https://eccc.weizmann.ac.il/report/2013/169