Monotone circuits for matching require linear depth
From MaRDI portal
Publication:4302809
DOI10.1145/146637.146684zbMath0799.68077OpenAlexW1966278576MaRDI QIDQ4302809
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/146637.146684
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (29)
Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Communication Lower Bounds via Critical Block Sensitivity ⋮ Communication complexity of approximate Nash equilibria ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ On the power of circuits with gates of low \(L_{1}\) norms. ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Average circuit depth and average communication complexity ⋮ Lower bounds for monotone \(q\)-multilinear Boolean circuits ⋮ Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation ⋮ Extension Complexity of Independent Set Polytopes ⋮ Clique problem, cutting plane proofs and communication complexity ⋮ The price of query rewriting in ontology-based data access ⋮ Strengthening convex relaxations of 0/1-sets using Boolean formulas ⋮ Negation-limited circuit complexity of symmetric functions ⋮ The direct sum of universal relations ⋮ On the power of small-depth threshold circuits ⋮ Natural proofs ⋮ On the mystery of negations in circuits: structure vs power ⋮ On derandomized composition of Boolean functions ⋮ New bounds for energy complexity of Boolean functions ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Random resolution refutations ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ Notes on Hazard-Free Circuits ⋮ Frege proof system and TNC° ⋮ Unnamed Item ⋮ An exponential gap with the removal of one negation gate ⋮ Reflections on Proof Complexity and Counting Principles
This page was built for publication: Monotone circuits for matching require linear depth
