2011/01/27 by Dana Ron, Ronitt Rubinfeld, Ron, Dana +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Binary logarithm #Boolean function #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Constant (computer programming) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Discrete mathematics #FOS: Computer and information sciences #Function (biology) #Machine Learning and Algorithms #Mathematical analysis #Mathematics #Monotone polygon #Multiplicative function #Omega #Optimization and Search Problems #Physics #Quantum mechanics #Simple (philosophy) #Upper and lower bounds #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1101.5345
published in arXiv (Cornell University) (Cornell University)
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/08/06
The em Total Influence ( em Average Sensitivity) of a discrete function\nis one of its fundamental measures. We study the problem of approximating the\ntotal influence of a monotone Boolean function ifnum plusminus=1 f:\n \±1 n longrightarrow \±1 , else f: bitsetn \→ bitset, fi\nwhich we denote by I[f]. We present a randomized algorithm that approximates\nthe influence of such functions to within a multiplicative factor of (1\±\n eps) by performing O(\(\√(n)\log n)/(I[f]) poly(1/ eps)) queries. %\n mnoteD: say something about technique? We also prove a lower bound of %\n\Ω(\(\√(n/\log n))/(I[f])) \Ω(\(\√(n))/(\log n \⋅\nI[f])) on the query complexity of any constant-factor approximation algorithm\nfor this problem (which holds for I[f] = \Ω(1)), % and I[f] =\nO(\√(n)/\log n)), hence showing that our algorithm is almost optimal in\nterms of its dependence on n. For general functions we give a lower bound of\n\Ω(\(n)/(I[f])), which matches the complexity of a simple sampling\nalgorithm.\n