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

Lecture notes in computer science

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

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein

Published Jan 1, 2011• 4 citations
Publisher
DOI
10.1007/978-3-642-22935-0_56

Related papers

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

Dana Ron, Ronitt Rubinfeld, Muli Safra +1 more

International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques•Aug 17, 2011•3 citations

How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Andris Ambainis, Ronald de Wolf

arXiv:1206.0717•Computational Complexity•May 8, 2014•11 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)O(\sqrt{n})O(n​) Query Complexity