The conjunctive complexity of quadratic Boolean functions
From MaRDI portal
Publication:808253
DOI10.1016/0304-3975(91)90194-7zbMATH Open0731.68049OpenAlexW2067227060MaRDI QIDQ808253FDOQ808253
Authors: Katja Lenz, Ingo Wegener 
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
Recommendations
circuit complexitymonotone circuitsNP completeconjunctive complexityquadratic Boolean functionssingle level complexity
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Decomposition of graphs and monotone formula size of homogeneous functions
- The monotone circuit complexity of Boolean functions
- Title not available (Why is that?)
- Constructing $O(n\log n)$ Size Monotone Formulae for the kth Threshold Function of n Boolean Variables
- Graph complexity
- Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
- On the coverings of graphs
- Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
- On the complexity of slice functions
- The multiplicative complexity of quadratic boolean forms
Cited In (8)
- Efficient Computation of the Best Quadratic Approximations of Cubic Boolean Functions
- The monotone circuit complexity of quadratic Boolean functions
- Algorithms and Computation
- Weighted Boolean Formula Games
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Title not available (Why is that?)
- Minimal polynomials for the conjunction of functions on disjoint variables can be very simple
- Quadratic sequential computations of Boolean mappings
This page was built for publication: The conjunctive complexity of quadratic Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808253)
