Formulas vs. circuits for small distance connectivity

DOI10.1145/2591796.2591828MaRDI QIDQ5259554zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• Formulas versus Circuits for Small Distance Connectivity
• Improved depth lower bounds for small distance connectivity
• scientific article; zbMATH DE number 4095383
• Monotone Circuits for Connectivity Have Depth (log n)^2-o(1)
• Threshold circuits of bounded depth

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(5)

• Formulas versus Circuits for Small Distance Connectivity
• Near-optimal small-depth lower bounds for small distance connectivity
• The average sensitivity of bounded-depth formulas
• On the optimality of Bellman-Ford-Moore shortest path algorithm
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)

Describes a project that uses

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)