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

arXiv:2608.00851

Block Sensitivity can exceed Spectral Sensitivity Squared

Alex Meiburg

Published Aug 1, 2026• 1 citation
arXivHTMLPDF

Abstract

The spectral sensitivity $λ(f)$ of a Boolean function is the largest eigenvalue of the adjacency matrix of its sensitivity graph. It lower-bounds every standard measure of query complexity, and Aaronson, Ben-David, Kothari, Rao and Tal, who introduced it, asked whether block sensitivity is at most quadratic in it: is $bs(f)=O(λ(f)^{2})$? We show that it is not. We construct a total Boolean function on $2017584$ variables with $bs(f)\ge 14011$ and $λ(f)\le 89.0162$, so that $bs(f)\geλ(f)^{2.127}$, and hence by composition a family with $λ(f_n)\to\infty$ and $bs(f_n)=Ω(λ(f_n)^{2.127})$. The function is the indicator of a union of $k$ subcubes indexed by the vertices of a doubly regular tournament, and the freedom left in the construction is fixed by the Lovász local lemma. The main result has been formally verified in Lean. We also give numerical evidence that a member of the same family on $1255$ variables reaches an exponent near $2.20$, and exhibit a member on $30$ variables whose exponent already exceeds $2$ and whose spectral sensitivity can be computed exactly.

DOI
10.48550/arxiv.2608.00851

Related papers

Comparing the Sensitivity and Degree of Boolean Functions via the Hypercube

Anne-Caroline Rupp

This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.

•Jun 1, 2026•0 citations

Improved Quantum Query Bounds for Boolean Matrix Product Verification

Amin Shiraz Gilani, François Le Gall, Xingyu Zhou

We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification ($\mathsf{BMPV}$), answering a longstanding open question in quantum query complexity. For $n\times n$ matrices, our upper bound is $\widetilde O(n^{17/12})$, improving on the standard $O(n^{3/2})$ bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an $Ω(n^{5/4})$ lower bound, which improves over the previous best known lower bound of $\widetildeΩ(n^{19/18})$ by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors ($\mathsf{OV}$), which asks whether an indexed list of $n$ Boolean vectors of dimension $n$ contains two vectors with disjoint supports. In particular, we prove equivalences between $\mathsf{OV}$ and $\mathsf{BMPV}$ and establish the above bounds for $\mathsf{OV}$. We also prove a tight $\widetilde Θ(n^{3/2})$ bound for a variant of $\mathsf{BMPV}$ that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.

quant-pharXiv:2609.40180•Oct 1, 2026•0 citations

Lower bounds on quantum query complexity for symmetric functions

Rajat Mittal, Sanjay S Nair, Sunayana Patro

One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.

•Oct 25, 2021•0 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

Subgraph detection asks whether an $n$-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph $H$. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of $H$ is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed $r\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/c})-o(1)}$ queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{r})$. Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.

quant-pharXiv:2609.40263•Oct 1, 2026•2 citations

On Fractional Block Sensitivity.

Raghav Kulkarni, Avishay Tal

In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal [Tal13] and Gilmer, Saks, and Srinivasan [GSS13] independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which was introduced by Aaronson [Aar03]. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity s(f) and approximate degree deg(f). As a consequence we obtain the following results: 1. We show that deg(f) = Ω( √ RC(f)), solving an open question posed by Aaronson [Aar03]. This also implies that deg(f) = Ω(QC(f)), where QC(f) is the quantum certificate complexity of f. As both deg(f) and QC(f) serve as lower bounds for the bounded error quantum query complexity, this shows that deg(f) is always a tighter lower bound compared to QC(f). 2. (a) We show that every transitive function on n variables must have RC(f) = Ω(n), QC(f) = Ω(n) and deg(f) = Ω(n), and note that all these bounds are tight. This is a strengthening of the previous lower bounds given by [SYZ04] and [Sun07]. (b) We show that Chakraborty’s [Cha11] example of a transitive function with s(f) = O(n) is optimal unless there is better than quadratic separation between the block sensitivity and the sensitivity. 3. Using fractional block sensitivity, we show that the zero error randomized decision tree complexity, R0(f), is upper bounded by O(R2(f) 2 · logR2(f)) where R2(f) is the two-sided bounded error randomized decision tree complexity of f . This improves the previous best relation between these two complexity measures given by Midrijanis [Mid05] of R0(f) = O(R2(f) 2 · log n) (where n is the number of variables). 4. We show that the (non-negative weight) adversary methods to lower bound the bounded error quantum query complexity of f can not give better bounds than √ RC(f)RC(f). This refines the earlier bound of √ C0(f)C1(f) by Spalek and Szegedy [SS06] and strengthens the so called certificate complexity barrier to its randomized analogue. ∗Centre for Quantum Technologies, Singapore Email: kulraghav@gmail.com †The Weizmann Institute of Science, Rehovot, Israel. Email: avishay.tal@weizmann.ac.il. Research supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities, by an Israel Science Foundation grant and by the Israeli Centers of Research Excellence (I-CORE) program. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 168 (2013)

Chicago Journal of Theoretical Computer Science•Jan 1, 2013•6 citations

Algorithms for Boolean Function Query Properties

Scott Aaronson

We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.

arXiv:cs/0107010•SIAM Journal on Computing•Jan 1, 2003•20 citations
The spectral sensitivity λ(f)λ(f)λ(f) of a Boolean function is the largest eigenvalue of the adjacency matrix of its sensitivity graph. It lower-bounds every standard measure of query complexity, and Aaronson, Ben-David, Kothari, Rao and Tal, who introduced it, asked whether block sensitivity is at most quadratic in it: is bs(f)=O(λ(f)2)bs(f)=O(λ(f)^{2})bs(f)=O(λ(f)2)? We show that it is not. We construct a total Boolean function on 201758420175842017584 variables with bs(f)≥14011bs(f)\ge 14011bs(f)≥14011 and λ(f)≤89.0162λ(f)\le 89.0162λ(f)≤89.0162, so that bs(f)≥λ(f)2.127bs(f)\geλ(f)^{2.127}bs(f)≥λ(f)2.127, and hence by composition a family with λ(fn)→∞λ(f_n)\to\inftyλ(fn​)→∞ and bs(fn)=Ω(λ(fn)2.127)bs(f_n)=Ω(λ(f_n)^{2.127})bs(fn​)=Ω(λ(fn​)2.127). The function is the indicator of a union of kkk subcubes indexed by the vertices of a doubly regular tournament, and the freedom left in the construction is fixed by the Lovász local lemma. The main result has been formally verified in Lean. We also give numerical evidence that a member of the same family on 125512551255 variables reaches an exponent near 2.202.202.20, and exhibit a member on 303030 variables whose exponent already exceeds 222 and whose spectral sensitivity can be computed exactly.
This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (BMPV\mathsf{BMPV}BMPV), answering a longstanding open question in quantum query complexity. For n×nn\times nn×n matrices, our upper bound is O~(n17/12)\widetilde O(n^{17/12})O(n17/12), improving on the standard O(n3/2)O(n^{3/2})O(n3/2) bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an Ω(n5/4)Ω(n^{5/4})Ω(n5/4) lower bound, which improves over the previous best known lower bound of Ω~(n19/18)\widetildeΩ(n^{19/18})Ω(n19/18) by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors (OV\mathsf{OV}OV), which asks whether an indexed list of nnn Boolean vectors of dimension nnn contains two vectors with disjoint supports. In particular, we prove equivalences between OV\mathsf{OV}OV and BMPV\mathsf{BMPV}BMPV and establish the above bounds for OV\mathsf{OV}OV. We also prove a tight Θ~(n3/2)\widetilde Θ(n^{3/2})Θ(n3/2) bound for a variant of BMPV\mathsf{BMPV}BMPV that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
Subgraph detection asks whether an nnn-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph HHH. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of HHH is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed r≥4r\ge 4r≥4, detecting the clique KrK_rKr​ requires nλr−o(1)n^{λ_r-o(1)}nλr​−o(1) queries, where λ4=19/18λ_4=19/18λ4​=19/18, the exponents λrλ_rλr​ increase strictly with rrr, and λr≥2−42/r+O(1/r)λ_r\ge 2-4\sqrt{2/r}+O(1/r)λr​≥2−42/r​+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph HHH with chromatic number c≥4c\ge 4c≥4. These bounds approach quadratic as ccc grows: for sufficiently large ccc, detection requires n2−O(log⁡log⁡c/c)−o(1)n^{2-O(\sqrt{\log\log c/c})-o(1)}n2−O(loglogc/c​)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,rK_{r,r}Kr,r​ requires nβr−o(1)n^{β_r-o(1)}nβr​−o(1) queries, where β10=181/180β_{10}=181/180β10​=181/180 and βr≥2−O(1/r)β_r\ge 2-O(1/\sqrt{r})βr​≥2−O(1/r​). Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.
In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal [Tal13] and Gilmer, Saks, and Srinivasan [GSS13] independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which was introduced by Aaronson [Aar03]. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity s(f) and approximate degree deg(f). As a consequence we obtain the following results: 1. We show that deg(f) = Ω( √ RC(f)), solving an open question posed by Aaronson [Aar03]. This also implies that deg(f) = Ω(QC(f)), where QC(f) is the quantum certificate complexity of f. As both deg(f) and QC(f) serve as lower bounds for the bounded error quantum query complexity, this shows that deg(f) is always a tighter lower bound compared to QC(f). 2. (a) We show that every transitive function on n variables must have RC(f) = Ω(n), QC(f) = Ω(n) and deg(f) = Ω(n), and note that all these bounds are tight. This is a strengthening of the previous lower bounds given by [SYZ04] and [Sun07]. (b) We show that Chakraborty’s [Cha11] example of a transitive function with s(f) = O(n) is optimal unless there is better than quadratic separation between the block sensitivity and the sensitivity. 3. Using fractional block sensitivity, we show that the zero error randomized decision tree complexity, R0(f), is upper bounded by O(R2(f) 2 · logR2(f)) where R2(f) is the two-sided bounded error randomized decision tree complexity of f . This improves the previous best relation between these two complexity measures given by Midrijanis [Mid05] of R0(f) = O(R2(f) 2 · log n) (where n is the number of variables). 4. We show that the (non-negative weight) adversary methods to lower bound the bounded error quantum query complexity of f can not give better bounds than √ RC(f)RC(f). This refines the earlier bound of √ C0(f)C1(f) by Spalek and Szegedy [SS06] and strengthens the so called certificate complexity barrier to its randomized analogue. ∗Centre for Quantum Technologies, Singapore Email: kulraghav@gmail.com †The Weizmann Institute of Science, Rehovot, Israel. Email: avishay.tal@weizmann.ac.il. Research supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities, by an Israel Science Foundation grant and by the Israeli Centers of Research Excellence (I-CORE) program. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 168 (2013)
We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.