Lower Bounds on Quantum Query Complexity for Read-Once Formulas with XOR and MUX Operators.
Hideaki FukuharaEiji TakimotoPublished in: IEICE Trans. Inf. Syst. (2010)
Keyphrases
- membership queries
- query complexity
- read once formulas
- concept class
- equivalence queries
- lower bound
- exact learning
- boolean functions
- uniform distribution
- learning algorithm
- dnf formulas
- efficient learning
- concept classes
- equivalence and membership queries
- dnf formulae
- target concept
- pac learning
- membership and equivalence queries
- upper bound
- vc dimension
- upper and lower bounds
- np hard
- objective function
- pattern languages
- statistical queries
- learning theory
- relational databases
- data streams
- databases