The complexity of depth-3 circuits computing symmetric Boolean functions.
Guy WolfovitzPublished in: Inf. Process. Lett. (2006)
Keyphrases
- boolean functions
- uniform distribution
- polynomial size
- truth table
- dnf formulae
- relevant variables
- prime implicants
- threshold functions
- multi valued
- worst case
- bounded treewidth
- dnf formulas
- functional properties
- decision problems
- disjunctive normal form
- read once formulas
- linear threshold
- high speed
- bi decomposition