Formulas vs. circuits for small distance connectivity

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 ( kn 3 ). 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: (i) It follows that polynomial-size circuits for Distance k ( n ) Connectivity require depth Ω(log k ) for all k ( n ) ≤ log log n . This matches the upper bound from recursive doubling and improves a previous Ω(log log k ) lower bound of Beame, Impagliazzo and Pitassi [BIP98]. (ii) We get a tight lower bound of s Ω( 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 ) ≤ log log log n . No lower bound better than s Ω(1) was previously known for any d ( n ) ≮ O (1). 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.

Authors

• Benjamin Rossman

Keywords

No keywords are indexed for this paper.