Combinatorics of monotone computations

DOI10.1007/S004930050046MaRDI QIDQ5928586zbMATH OpenOpenAlexFDO

Authors Stasys Jukna

Publication date 1 April 2001

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004930050046

zbMATH Keywords

bipartite Paley graphsBoolean functionsclique-like graph functionscutting planes proofexponential lower boundsmonotone circuitsmonotone computationspartial \(t\)-designssuper-polynomial lower bounds

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Structure of proofs (03F07) Transversal (matching) theory (05D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05)

Recommendations

• An exponential lower bound for the size of monotone real circuits
• Fundamentals of Computation Theory
• Monotone real circuits are more powerful than monotone Boolean circuits
• scientific article; zbMATH DE number 4049557
• The monotone circuit complexity of Boolean functions

Cited in

(21)

• A note on monotone complexity and the rank of matrices
• On the minimum number of negations leading to super-polynomial savings
• A note on monotone real circuits
• The gap between monotone and non-monotone circuit complexity is exponential
• On the incompressibility of monotone DNFs
• Lower bounds for Boolean circuits of bounded negation width
• Lower bounds for monotone real circuit depth and formula size and tree-like cutting planes
• Higher lower bounds on monotone size
• On Negations in Boolean Networks
• scientific article; zbMATH DE number 4049557 (Why is no real title available?)
• Cutting planes cannot approximate some integer programs
• Communication lower bounds via critical block sensitivity
• scientific article; zbMATH DE number 6928782 (Why is no real title available?)
• Lower bounds for tropical circuits and dynamic programs
• Strongly exponential lower bounds for monotone computation
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• Monotone circuit lower bounds from resolution
• Communication lower bounds via critical block sensitivity
• Fundamentals of Computation Theory
• Monotone circuit lower bounds from robust sunflowers
• Secret sharing, slice formulas, and monotone real circuits

This page was built for publication: Combinatorics of monotone computations

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