22 citations · 22 across the 1 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-ph2002
A lower bound on the quantum query complexity of read-once functions
Howard Barnum, Michael Saks
We establish a lower bound of on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $Ω(\sqrt{D(f)…