Formulas versus Circuits for Small Distance Connectivity

DOI10.1137/15M1027310zbMATH Open1402.68076OpenAlexW2898993321MaRDI QIDQ4554075FDOQ4554075

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

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

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)

Cites Work

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

Cited In (4)

• Formulas vs. circuits for small distance connectivity
• A polynomial excluded-minor approximation of treedepth
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• 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)