72 citations · 94 across the 2 of their papers we have counts for
2 papers
cs.CC2005★ 22 cited
Every decision tree has an influential variable
Ryan O'Donnell, Michael Saks, Oded Schramm +1
We prove that for any decision tree calculating a boolean function , \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where is the probability that the…
quant-ph2004★ 72 cited
Improved Bounds on Quantum Learning Algorithms
Alp Atici, Rocco A. Servedio
In this article we give several new results on the complexity of algorithms that learn Boolean functions from quantum queries and quantum examples. Hunziker et al. conjectured that…