Math @ Duke

Publications [#348685] of Benjamin Rossman
Papers Published
 Rossman, B, Formulas vs. circuits for small distance connectivity,
Proceedings of the Annual Acm Symposium on Theory of Computing
(January, 2014),
pp. 203212, ISBN 9781450327107 [doi]
(last updated on 2022/05/19)
Abstract: We give the first superpolynomial separation in the power of boundeddepth boolean formulas vs. circuits. Specifically, we consider the problem Distance κ (n) Connectivity, which asks whether two specified nodes in a graph of size n are connected by a path of length at most κ(n). This problem is solvable (by the recursive doubling technique) on circuits of depth O(log κ) and size O(κn3). In contrast, we show that solving this problem on formulas of depth log n/(log log n)O(1) requires size nΩ(log κ) for all κ (n) ≤ log log n. As corollaries: (i) It follows that polynomialsize circuits for Distance κ (n) Connectivity require depth Ω(log κ) for all κ (n) ≤ log log n. This matches the upper bound from recursive doubling and improves a previous Ω(log log κ) lower bound of Beame, Impagliazzo and Pitassi [BIP98]. (ii) We get a tight lower bound of sΩ(d) on the size required to simulate sizes depthd circuits by depthd formulas for all s(n) = nO(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 boundeddepth formulas solving Distance κ(n) Connectivity imply upper bounds on pathset complexity. The other half is a combinatorial lower bound on pathset complexity. © 2014 ACM.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

