Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-033 | 8th March 2011 07:54

The influence lower bound via query elimination

RSS-Feed




TR11-033
Authors: Rahul Jain, Shengyu Zhang
Publication: 13th March 2011 22:15
Downloads: 3237
Keywords: 


Abstract:

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized 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 distributional query complexity of $f$, and it allows an immediate extension which can be used to prove stronger lower bounds for some functions.



ISSN 1433-8092 | Imprint