2011/02/23 by Rahul Jain, Shengyu Zhang, Jain, Rahul +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Machine Learning and Algorithms #cs.CC
paper · pdf · doi:10.48550/arxiv.1102.4699
5 pages
arxiv created 2011/02/23 · openalex publication_date 2011/02/23 · arxiv updated 2011/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.