2011/01/27 by Dana Ron, Ronitt Rubinfeld, Ron, Dana +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1101.5345
arxiv created 2011/01/27 · openalex publication_date 2011/01/27 · arxiv updated 2011/01/28 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
The \em Total Influence (\em Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function \ifnum\plusminus=1 f: \±1\n \longrightarrow \±1\, \else f: \bitsetn → \bitset, \fi which we denote by I[f]. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of (1± \eps) by performing O((√(n)log n)/(I[f]) \poly(1/\eps)) queries. % \mnoteD: say something about technique? We also prove a lower bound of % Ω((√(n/log n))/(I[f])) Ω((√(n))/(log n ⋅ I[f])) on the query complexity of any constant-factor approximation algorithm for this problem (which holds for I[f] = Ω(1)), % and I[f] = O(√(n)/log n)), hence showing that our algorithm is almost optimal in terms of its dependence on n. For general functions we give a lower bound of Ω((n)/(I[f])), which matches the complexity of a simple sampling algorithm.