Formulas versus Circuits for Small Distance Connectivity
From MaRDI portal
Publication:4554075
DOI10.1137/15M1027310zbMath1402.68076OpenAlexW2898993321MaRDI QIDQ4554075
Publication date: 7 November 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1027310
lower boundscircuitscircuit complexityBoolean formulasbounded depthformulasst-connectivity\(\mathsf{AC}^0\)
Related Items (2)
A polynomial excluded-minor approximation of treedepth ⋮ Tree-Depth and the Formula Complexity of Subgraph Isomorphism
Cites Work
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- First-order definability on finite structures
- Improved depth lower bounds for small distance connectivity
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- Lower bounds on arithmetic circuits via partial derivatives
- The average sensitivity of bounded-depth formulas
- Relationships between nondeterministic and deterministic tape complexities
- On the Power of Homogeneous Depth 4 Arithmetic Circuits
- Parity, circuits, and the polynomial-time hierarchy
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Undirected connectivity in log-space
- On the depth complexity of formulas
- Poisson approximation for large deviations
- Approximation and Small-Depth Frege Proofs
- Tight Lower Bounds for st-Connectivity on the NNJAG Model
- The Shrinkage Exponent of de Morgan Formulas is 2
- The number of Boolean functions computed by formulas of a given size
- The complexity of graph connectivity
- Near-optimal small-depth lower bounds for small distance connectivity
This page was built for publication: Formulas versus Circuits for Small Distance Connectivity
