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
(36)- On the power of circuits with gates of low \(L_{1}\) norms.
- Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
- An exponential gap with the removal of one negation gate
- Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
- The direct sum of universal relations
- On the mystery of negations in circuits: structure vs power
- Strengthening convex relaxations of 0/1-sets using Boolean formulas
- On derandomized composition of Boolean functions
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Random resolution refutations
- The price of query rewriting in ontology-based data access
- Lower bounds for Boolean circuits of bounded negation width
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Monotone Circuits for Connectivity Require Super-Logarithmic Depth
- Monotone Circuits for Connectivity Have Depth (log n)2-o(1)
- scientific article; zbMATH DE number 1263233 (Why is no real title available?)
- Communication lower bounds via critical block sensitivity
- Clique problem, cutting plane proofs and communication complexity
- Randomized feasible interpolation and monotone circuits with a local oracle
- Extension complexity of independent set polytopes
- Testing k-monotonicity
- Notes on hazard-free circuits
- Reflections on Proof Complexity and Counting Principles
- Lower Bounds for DeMorgan Circuits of Bounded Negation Width
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Natural proofs
- New bounds for energy complexity of Boolean functions
- Frege proof system and TNC°
- Average circuit depth and average communication complexity
- Lower bounds for monotone q-multilinear Boolean circuits
- Negation-limited circuit complexity of symmetric functions
- On the power of small-depth threshold circuits
- Separations in proof complexity and TFNP
- On protocols for monotone feasible interpolation
- Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract)
- Multiparty communication complexity of collision-finding and cutting planes proofs of concise pigeonhole principles
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)
