Complexity of Boolean Functions Over Bases with Unbounded Fan-In Gates.
Vlado DancíkPublished in: Inf. Process. Lett. (1996)
Keyphrases
- boolean functions
- uniform distribution
- polynomial size
- threshold functions
- membership queries
- worst case
- relevant variables
- functional properties
- multi valued
- dnf formulae
- linear threshold
- prime implicants
- read once formulas
- computational complexity
- bounded treewidth
- disjunctive normal form
- pseudo boolean functions