Math @ Duke

Publications [#348670] of Benjamin Rossman
Papers Published
 Rossman, B, Formulas versus circuits for small distance connectivity,
Siam Journal on Computing, vol. 47 no. 5
(January, 2018),
pp. 19862028 [doi]
(last updated on 2022/05/19)
Abstract: We prove an nΩ (log k) lower bound on the AC0formula size of Distance k(n) Connectivity for all k(n) ≤ log log n and formulas up to depth log n/(log log n)O(1). This lower bound strongly separates the power of boundeddepth formulas versus circuits, since Distance k(n) Connectivity is solvable by polynomialsize AC0circuits of depth O(log k). For all d(n) ≤ log log log n, it follows that polynomialsize depthd circuitswhich are a semantic subclass of nO(d)size depthd formulasare not a semantic subclass of no(d)size formulas of much higher depth log n/(log log n)O(1). Our lower bound technique probabilistically associates each gate in an AC0 formula with an object called a pathset. We show that with high probability these random pathsets satisfy a family of density constraints called smallness, a property akin to low average sensitivity. We then study a complexity measure on small pathsets, which lower bounds the AC0 formula size of Distance k(n) Connectivity. The heart of our technique is an nΩ (log k) lower bound on this pathset complexity measure.


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

