Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Approximating the influence of monotone boolean functions in O(√n) query complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein

Published Aug 17, 2011• 3 citations
OpenAlex

Related papers

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

Lecture notes in computer science•Jan 1, 2011•4 citations

Average-case query complexity of fixed-weight boolean functions and k-CNFs

Yuan Li, Mingjun Liu, Haowei Wu +1 more

Theoretical Computer Science•Aug 8, 2026•0 citations

Query Complexity of Boolean Functions on the Middle Slice of the Cube

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy +4 more

•Jan 1, 2023•0 citations

Quantum Query Complexity of Boolean Functions with Small On-Sets

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi +4 more

Lecture notes in computer science•Jan 1, 2008•11 citations

Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Queries

Mark Chen, Xi Chen, Hao Cui +2 more

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•2 citations

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity

Dana Ron, Ronitt Rubinfeld, Muli Safra +2 more

The Total Influence ( 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, 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 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), 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.

arXiv:1101.5345•ACM Transactions on Computation Theory•Nov 1, 2012•29 citations
Approximating the Influence of Monotone Boolean Functions in O(n)O(\sqrt{n})O(n​) Query Complexity
The Total Influence ( 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, 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 ± ε ) by performing O (√ n I [ f ] poly(1/ ε )) queries. We also prove a lower bound of Ω (√ n log n · I [ f ]) on the query complexity of any constant factor approximation algorithm for this problem (which holds for I [ f ]= Ω (1)), 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.