The conjunctive complexity of quadratic Boolean functions
From MaRDI portal
Publication:808253
DOI10.1016/0304-3975(91)90194-7zbMath0731.68049MaRDI QIDQ808253
Publication date: 1991
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(91)90194-7
monotone circuits; circuit complexity; NP complete; conjunctive complexity; quadratic Boolean functions; single level complexity
68Q25: Analysis of algorithms and problem complexity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
- On the complexity of slice functions
- Decomposition of graphs and monotone formula size of homogeneous functions
- The monotone circuit complexity of Boolean functions
- On the coverings of graphs
- The multiplicative complexity of quadratic boolean forms
- Approximation algorithms for combinatorial problems
- Graph complexity
- Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables