Combinatorics of monotone computations

DOI10.1007/s004930050046zbMath0962.03030OpenAlexW2043686677MaRDI QIDQ5928586

Stasys P. 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

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

Related Items (7)

Lower bounds for Boolean circuits of bounded negation width ⋮ Cutting planes cannot approximate some integer programs ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ On Negations in Boolean Networks ⋮ On the minimum number of negations leading to super-polynomial savings ⋮ Monotone circuit lower bounds from robust sunflowers

This page was built for publication: Combinatorics of monotone computations