Formulas versus Circuits for Small Distance Connectivity

DOI10.1137/15M1027310MaRDI QIDQ4554075zbMATH OpenOpenAlexFDO

Authors 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 boundscircuit complexitycircuitsBoolean formulasbounded depthformulasst-connectivity\(\mathsf{AC}^0\)

Mathematics Subject Classification ID

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

Recommendations

• Formulas vs. circuits for small distance connectivity
• Singular distance powers of circuits
• scientific article; zbMATH DE number 90711
• Separation of multilinear circuit and formula size
• scientific article; zbMATH DE number 3985121
• On the eigenvalues of distance powers of circuits
• Connectivity calculus
• On circuits in graphs
• Circuit principles and weak pigeonhole variants

Cites work

• scientific article; zbMATH DE number 6829287 (Why is no real title available?)
• scientific article; zbMATH DE number 5485586 (Why is no real title available?)
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• Approximation and Small-Depth Frege Proofs
• Boolean function complexity. Advances and frontiers.
• First-order definability on finite structures
• Improved depth lower bounds for small distance connectivity
• Lower bounds on arithmetic circuits via partial derivatives
• Monotone Circuits for Connectivity Require Super-Logarithmic Depth
• Near-optimal small-depth lower bounds for small distance connectivity
• On the depth complexity of formulas
• On the power of homogeneous depth 4 arithmetic circuits
• Parity, circuits, and the polynomial-time hierarchy
• Poisson approximation for large deviations
• Relationships between nondeterministic and deterministic tape complexities
• The Shrinkage Exponent of de Morgan Formulas is 2
• The average sensitivity of bounded-depth formulas
• The complexity of graph connectivity
• The number of Boolean functions computed by formulas of a given size
• Tight Lower Bounds for st-Connectivity on the NNJAG Model
• Undirected connectivity in log-space

Cited in

(4)

• A polynomial excluded-minor approximation of treedepth
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Formulas vs. circuits for small distance connectivity
• Near-optimal small-depth lower bounds for small distance connectivity

This page was built for publication: Formulas versus Circuits for Small Distance Connectivity

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