2013/12/02 by Benjamin Rossman, Rossman, Benjamin
Computer Science · #68Q15 #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #acm:68Q15 #cs.CC #msc:68Q15
paper · pdf · doi:10.48550/arxiv.1312.0355
arxiv created 2013/12/02 · arxiv updated 2013/12/03
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 \bf circuits of depth O(log k) and size O(kn3). In contrast, we show that solving this problem on \bf formulas of depth log n/(loglog n)O(1) requires size nΩ(log k) for all k(n) ≤ loglog n. As corollaries: (i) It follows that polynomial-size circuits for Distance k(n) Connectivity require depth Ω(log k) for all k(n) ≤ loglog n. This matches the upper bound from recursive doubling and improves a previous Ω(loglog k) lower bound of Beame, Pitassi and Impagliazzo [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) = nO(1) and d(n) ≤ logloglog n. No lower bound better than sΩ(1) was previously known for any d(n) \nleq 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.