The monotone circuit complexity of boolean functions

1987/03/01 by Noga Alon, Ravi B. Boppana · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Boolean circuit #Boolean function #Circuit complexity #Clique #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Electronic circuit #Exponential function #Function (biology) #Graph #Machine Learning and Algorithms #Mathematical analysis #Mathematics #Monotone polygon #Upper and lower bounds

paper · doi:10.1007/bf02579196

crossref issued 1987/03/01 · crossref published 1987/03/01 · crossref published-print 1987/03/01 · openalex publication_date 1987/03/01 · crossref created 2007/03/22 · crossref deposited 2019/05/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/15 · crossref indexed 2026/07/16

Citations

• An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs

Cited by

• Resolution over linear equations and multilinear proofs
• Approximating clique is almost NP-complete
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
• Claw-free graphs — A survey
• On Promise Problems: A Survey
• Natural Proofs
• Clique problem [wikipedia]