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

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

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy, Kartal Nagy, Dömötör Pálvölgyi, Balázs Patkós, Gábor Wiener

Published Jan 1, 2023• 0 citations
Publisher
DOI
10.2139/ssrn.4615972

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

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

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

A Framework for Ruling Out Quantum Speedups

Thomas Huffstutler, Upendra Kapshikar, David Miloschewsky +1 more

We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two complementary lenses: promise-aware complexity measures and function completions. First, we introduce promise versions of standard combinatorial measures (including block sensitivity and related variants) and prove that if the relevant promise and completion measures ``collapse'', then deterministic and quantum query complexities are necessarily polynomially related, i.e. $D(f) = \mathrm{poly}(Q(f))$. We then analyze structured families of promises, including symmetric partial functions and promises supported on Hamming slices, obtaining sharp (up to polynomial factors) characterizations in terms of a single gap parameter for the symmetric case and refined slice-dependent bounds for $k$-slice domains. Next, we formalize completion complexity as the minimum of a measure over total completions of a partial function, and show that completability of a measure captures the possibility of superpolynomial quantum speedups. Finally, we apply this viewpoint to derive broad non-speedup criteria for some classes of functions admitting well-behaved completions, such as functions defined on a single slice or a union of slices, functions with low maximum influence on both the standard and $p$-biased hypercubes and functions with efficiently identifiable domains, and then show some hardness results for general completion techniques.

quant-pharXiv:2603.29256•Leibniz international proceedings in informatics•Apr 1, 2026•2 citations

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

Query complexity of Boolean functions on the middle slice of the cube

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

We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and 1's in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.

arXiv:2309.13678•Sep 24, 2023•0 citations
We study when partial Boolean functions can (and cannot) exhibit superpolynomial quantum query speedups, and develop a general framework for ruling out such speedups via two complementary lenses: promise-aware complexity measures and function completions. First, we introduce promise versions of standard combinatorial measures (including block sensitivity and related variants) and prove that if the relevant promise and completion measures ``collapse'', then deterministic and quantum query complexities are necessarily polynomially related, i.e. D(f)=poly(Q(f))D(f) = \mathrm{poly}(Q(f))D(f)=poly(Q(f)). We then analyze structured families of promises, including symmetric partial functions and promises supported on Hamming slices, obtaining sharp (up to polynomial factors) characterizations in terms of a single gap parameter for the symmetric case and refined slice-dependent bounds for kkk-slice domains. Next, we formalize completion complexity as the minimum of a measure over total completions of a partial function, and show that completability of a measure captures the possibility of superpolynomial quantum speedups. Finally, we apply this viewpoint to derive broad non-speedup criteria for some classes of functions admitting well-behaved completions, such as functions defined on a single slice or a union of slices, functions with low maximum influence on both the standard and ppp-biased hypercubes and functions with efficiently identifiable domains, and then show some hardness results for general completion techniques.
Approximating the Influence of Monotone Boolean Functions in O(n)O(\sqrt{n})O(n​) Query Complexity
We study the query complexity on slices of Boolean functions. Among other results we show that there exists a Boolean function for which we need to query all but 7 input bits to compute its value, even if we know beforehand that the number of 0's and 1's in the input are the same, i.e., when our input is from the middle slice. This answers a question of Byramji. Our proof is non-constructive, but we also propose a concrete candidate function that might have the above property. Our results are related to certain natural discrepancy type questions that, somewhat surprisingly, have not been studied before.