Theory of Computing
-------------------
Title     : The Influence Lower Bound Via Query Elimination
Authors   : Rahul Jain and Shengyu Zhang
Volume    : 7
Number    : 10
Pages     : 147-153
URL       : https://theoryofcomputing.org/articles/v007a010

Abstract
--------

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.