Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory.
Rusins FreivaldsLiva GarkajePublished in: ISMVL (2007)
Keyphrases
- boolean functions
- complexity theory
- statistical queries
- disjunctive normal form
- threshold functions
- uniform distribution
- dnf formulae
- polynomial size
- theoretical basis
- query evaluation
- dnf formulas
- low degree
- query processing
- membership queries
- prime implicants
- functional properties
- data structure
- computational geometry
- binary decision diagrams
- multi valued
- machine learning
- quantum computing
- term dnf
- read once formulas
- learning algorithm