The Monotone Circuit Complexity of Quadratic Boolean Functions.
Kazuyuki AmanoAkira MaruokaPublished in: Algorithmica (2006)
Keyphrases
- boolean functions
- pseudo boolean functions
- uniform distribution
- polynomial size
- truth table
- computational complexity
- linear functions
- relevant variables
- threshold functions
- dnf formulae
- multi valued
- membership queries
- objective function
- disjunctive normal form
- prime implicants
- read once formulas
- monotone boolean functions
- worst case
- bounded treewidth
- linear threshold
- decision trees
- functional properties
- high speed