Formulas versus Circuits for Small Distance Connectivity

DOI10.1137/15M1027310zbMath1402.68076OpenAlexW2898993321MaRDI QIDQ4554075

Benjamin Rossman

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

zbMATH Keywords

lower boundscircuitscircuit complexityBoolean formulasbounded depthformulasst-connectivity\(\mathsf{AC}^0\)

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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