Optimal quantum query bounds for almost all Boolean functions.
Andris AmbainisArturs BackursJuris SmotrovsRonald de WolfPublished in: STACS (2013)
Keyphrases
- propositional logic
- boolean functions
- uniform distribution
- linear threshold
- dnf formulae
- worst case
- threshold functions
- query evaluation
- disjunctive normal form
- query processing
- database
- prime implicants
- statistical queries
- upper bound
- lower bound
- relevant variables
- membership queries
- optimal solution
- linear functions
- multi valued
- read once formulas
- np complete