Almost k-wise independence and hard Boolean functions.
Valentine KabanetsPublished in: Theor. Comput. Sci. (2003)
Keyphrases
- boolean functions
- uniform distribution
- randomly generated
- threshold functions
- functional properties
- dnf formulae
- membership queries
- prime implicants
- pairwise
- multi valued
- binary decision diagrams
- relevant variables
- disjunctive normal form
- truth table
- machine learning
- read once formulas
- linear functions
- linear threshold
- random instances
- conditional independence
- search space