Monotone circuits for matching require linear depth
From MaRDI portal
Recommendations
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Monotone circuit lower bounds from resolution
- Monotone circuit lower bounds from resolution
- Size-depth trade-offs for monotone arithmetic circuits
- scientific article; zbMATH DE number 4062595
- Threshold functions and bounded depth monotone circuits
- Efficient monotone circuits for threshold functions
- Lower bounds on monotone arithmetic circuits with restricted depths
- Monotone circuits for monotone weighted threshold functions
Cited in
(33)- Reflections on Proof Complexity and Counting Principles
- On the power of circuits with gates of low \(L_{1}\) norms.
- The price of query rewriting in ontology-based data access
- Frege proof system and TNC°
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Separations in proof complexity and TFNP
- Testing k-monotonicity
- An exponential gap with the removal of one negation gate
- On the mystery of negations in circuits: structure vs power
- The direct sum of universal relations
- Lower bounds for monotone q-multilinear Boolean circuits
- On the power of small-depth threshold circuits
- On protocols for monotone feasible interpolation
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
- Clique problem, cutting plane proofs and communication complexity
- Natural proofs
- Lower bounds for Boolean circuits of bounded negation width
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- On derandomized composition of Boolean functions
- Notes on hazard-free circuits
- Randomized feasible interpolation and monotone circuits with a local oracle
- Average circuit depth and average communication complexity
- Strengthening convex relaxations of 0/1-sets using Boolean formulas
- Extension complexity of independent set polytopes
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- Lower Bounds for DeMorgan Circuits of Bounded Negation Width
- Random resolution refutations
- Negation-limited circuit complexity of symmetric functions
- New bounds for energy complexity of Boolean functions
- Communication lower bounds via critical block sensitivity
This page was built for publication: Monotone circuits for matching require linear depth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302809)
