Volume 7 (2011)
Article 10 pp. 147-153
[Note]
The Influence Lower Bound Via Query Elimination
Received: March 4, 2011
Published: July 19, 2011
Published: July 19, 2011
Keywords: randomized query complexity, influence of variables
Categories: note, complexity theory, Boolean functions, lower bounds, decision tree, sensitivity, query complexity, randomized, randomized query complexity, influence, OSSS inequality
ACM Classification: F.1.3
AMS Classification: 68Q17
Abstract: [Plain Text Version]
We give a simple proof, via query elimination, of a result due to O'Donnell, Saks, Schramm, and Servedio, which shows a lower bound on the zero-error expected query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to the two-sided error expected query complexity of $f$, and it allows an immediate extension which can be used to prove stronger lower bounds for some functions.