Higher lower bounds on monotone size

DOI10.1145/335305.335349zbMATH Open1296.68069OpenAlexW2009546904MaRDI QIDQ3192005FDOQ3192005

Authors: D. 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

Recommendations

• Strongly exponential lower bounds for monotone computation
• scientific article; zbMATH DE number 4049557
• An exponential lower bound for the size of monotone real circuits
• The monotone circuit complexity of Boolean functions
• Combinatorics of monotone computations

Mathematics Subject Classification ID

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

Cited In (13)

• Lower bounds for monotonic list labeling
• Reductions for monotone Boolean circuits
• On the incompressibility of monotone DNFs
• A stronger LP bound for formula size lower bounds via clique constraints
• Monotone circuit lower bounds from robust sunflowers
• Negation-limited formulas
• Linear-size log-depth negation-limited inverter for \(k\)-tonic binary sequences
• On Negations in Boolean Networks
• Negation-limited complexity of parity and inverters
• Fundamentals of Computation Theory
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• A lower bound for monotone perceptrons
• A characterization of span program size and improved lower bounds for monotone span programs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192005)