Combinatorics of monotone computations
Publication:5928586
DOI10.1007/s004930050046zbMath0962.03030MaRDI QIDQ5928586
Publication date: 1 April 2001
Published in: Combinatorica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s004930050046
bipartite Paley graphs; Boolean functions; clique-like graph functions; cutting planes proof; exponential lower bounds; monotone circuits; monotone computations; partial \(t\)-designs; super-polynomial lower bounds
68R05: Combinatorics in computer science
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
03F07: Structure of proofs
05D15: Transversal (matching) theory
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items