Higher lower bounds on monotone size

DOI10.1145/335305.335349zbMath1296.68069OpenAlexW2009546904MaRDI QIDQ3192005

Danny Harnik, Ran Raz

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335349

Mathematics Subject Classification ID

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

Related Items (7)

Reductions for monotone Boolean circuits ⋮ Negation-limited formulas ⋮ Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences ⋮ Negation-limited complexity of parity and inverters ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ On Negations in Boolean Networks ⋮ Monotone circuit lower bounds from robust sunflowers

This page was built for publication: Higher lower bounds on monotone size