The monotone circuit complexity of Boolean functions

DOI10.1007/BF02579196zbMath0631.68041DBLPjournals/combinatorica/AlonB87OpenAlexW2012476164WikidataQ30000144 ScholiaQ30000144MaRDI QIDQ1094870

Ravi B. Boppana, Noga Alon

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

Boolean functionscliquesexponential lower boundcomplexity of monotone circuitsNP-functionsuperpolynomial lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (97)

Affine projections of symmetric polynomials. ⋮ Discretely ordered modules as a first-order extension of the cutting planes proof system ⋮ On the automatizability of resolution and related propositional proof systems ⋮ Monotone real circuits are more powerful than monotone Boolean circuits ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Limiting negations in non-deterministic circuits ⋮ Feasible Interpolation for QBF Resolution Calculi ⋮ Some complete and intermediate polynomials in algebraic complexity theory ⋮ Lower bounds on the size of bounded depth circuits over a complete basis with logical addition ⋮ Lower bounds for monotone counting circuits ⋮ On almost bad Boolean bases ⋮ Secret Sharing for mNP: Completeness Results ⋮ Applications of matrix methods to the theory of lower bounds in computational complexity ⋮ Claw-free graphs---a survey ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice ⋮ A lower bound for read-once-only branching programs ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ Circuit Complexity Meets Ontology-Based Data Access ⋮ If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser ⋮ Randomized feasible interpolation and monotone circuits with a local oracle ⋮ On sunflowers and matrix multiplication ⋮ Dag-like communication and its applications ⋮ On monotone simulations on nonmonotone networks ⋮ A lower bound for intuitionistic logic ⋮ Independence and matching numbers of unicyclic graphs from null space ⋮ Sunflowers and testing triangle-freeness of functions ⋮ Bounds in ontology-based data access via circuit complexity ⋮ Lower bounds for Boolean circuits of bounded negation width ⋮ Shadows of Newton polytopes ⋮ Towards NP-P via proof complexity and search ⋮ Lower bounds for monotone \(q\)-multilinear Boolean circuits ⋮ Satisfiability, branch-width and Tseitin tautologies ⋮ Acyclicity programming for sigma-protocols ⋮ A sorting network in bounded arithmetic ⋮ Cutting planes cannot approximate some integer programs ⋮ Clique problem, cutting plane proofs and communication complexity ⋮ Finding a smallest odd hole in a claw-free graph using global structure ⋮ The canonical pairs of bounded depth Frege systems ⋮ Positive Neural Networks in Discrete Time Implement Monotone-Regular Behaviors ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Lower bounds for depth-restricted branching programs ⋮ An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams ⋮ Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic ⋮ The price of query rewriting in ontology-based data access ⋮ Very large cliques are easy to detect ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Negation-limited circuit complexity of symmetric functions ⋮ A note on the power of majority gates and modular gates ⋮ The splitting power of branching programs of bounded repetition and CNFs of bounded width ⋮ Lower bounds for cutting planes proofs with small coefficients ⋮ Lower bounds for resolution and cutting plane proofs and monotone computations ⋮ A simple lower bound for monotone clique using a communication game ⋮ Lower bounds for monotone span programs ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Resolution over linear equations and multilinear proofs ⋮ On the power of small-depth threshold circuits ⋮ One-way permutations, computational asymmetry and distortion. ⋮ Logic circuits from zero forcing ⋮ Lower bounds for modal logics ⋮ On the complexity of cutting-plane proofs using split cuts ⋮ Natural proofs ⋮ On the mystery of negations in circuits: structure vs power ⋮ Unprovability of strong complexity lower bounds in bounded arithmetic ⋮ Proof complexity of substructural logics ⋮ Negation-limited formulas ⋮ Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 ⋮ On lengths of proofs in non-classical logics ⋮ Notes on Boolean read-\(k\) and multilinear circuits ⋮ Approximation Limitations of Pure Dynamic Programming ⋮ Proof Complexity of Non-classical Logics ⋮ A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The gap between monotone and non-monotone circuit complexity is exponential ⋮ Substitution Frege and extended Frege proof systems in non-classical logics ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Lower Bounds for DeMorgan Circuits of Bounded Negation Width ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ On Negations in Boolean Networks ⋮ Non-cancellative Boolean circuits: A generalization of monotone boolean circuits ⋮ On the bottleneck counting argument ⋮ Notes on Hazard-Free Circuits ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An exponential lower bound for the size of monotone real circuits ⋮ On the number of ANDs versus the number of ORs in monotone Boolean circuits ⋮ Lower bounds for the weak pigeonhole principle and random formulas beyond resolution ⋮ Monotone circuit lower bounds from robust sunflowers ⋮ A feasible interpolation for random resolution ⋮ On the negation-limited circuit complexity of merging ⋮ The conjunctive complexity of quadratic Boolean functions ⋮ An exponential gap with the removal of one negation gate

Cites Work

• Unnamed Item
• Unnamed Item
• A Boolean function requiring 3n network size
• A 4n-lower bound on the monotone network complexity of a one-output Boolean function
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• Intersection Theorems for Systems of Sets
• A complexity theory based on Boolean algebra
• The Power of Negative Thinking in Multiplying Boolean Matrices
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: The monotone circuit complexity of Boolean functions