Higher lower bounds on monotone size

DOI10.1145/335305.335349MaRDI QIDQ3192005zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(14)

• Lower bounds for monotonic list labeling
• Reductions for monotone Boolean circuits
• Strongly exponential lower bounds for monotone computation
• A stronger LP bound for formula size lower bounds via clique constraints
• On the incompressibility of monotone DNFs
• 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)