Formulas vs. circuits for small distance connectivity

DOI10.1145/2591796.2591828zbMATH Open1315.68158arXiv1312.0355OpenAlexW1975173196MaRDI QIDQ5259554FDOQ5259554

Benjamin Rossman

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: 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 {�f circuits} of depth $O(logk)$ and size $O(k{n}^3)$. In contrast, we show that solving this problem on {�f formulas} of depth $logn/(loglogn{)}^{O(1)}$ requires size $n^{Omega(logk)}$ for all $k(n)leqloglogn$. As corollaries: (i) It follows that polynomial-size circuits for Distance $k(n)$ Connectivity require depth $Omega(logk)$ for all $k(n)leqloglogn$. This matches the upper bound from recursive doubling and improves a previous $Omega(loglogk)$ 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)leqlogloglogn$. No lower bound better than $s^{Omega(1)}$ was previously known for any $d(n)leqO(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.

Full work available at URL: https://arxiv.org/abs/1312.0355

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (4)

• On the optimality of Bellman-Ford-Moore shortest path algorithm
• The average sensitivity of bounded-depth formulas
• Formulas versus Circuits for Small Distance Connectivity
• Title not available (Why is that?)

Uses Software

• SuLQ

This page was built for publication: Formulas vs. circuits for small distance connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259554)