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• 0 citations
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

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

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

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

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•5 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•17 citations

Spectral Properties of Boolean Functions, Graphs and Graph States

Constanza Riera

Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.

•Jan 1, 2005•5 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.
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.
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.
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.
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.
Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.