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.