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

Chicago Journal of Theoretical Computer Science

On Fractional Block Sensitivity.

Raghav Kulkarni, Avishay Tal

Published Jan 1, 2013• 5 citations
OpenAlex

Abstract

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)

Related papers

All Classical Adversary Methods Are Equivalent for Total Functions

Andris Ambainis, Martins Kokainis, Krišjānis Prūsis +2 more

We show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than √ n ⋅ bs( f ), where n is the number of variables and bs( f ) is the block sensitivity. Then, we exhibit a partial function f that matches this upper bound, fbs( f ) = Ω (√ n ⋅ bs( f )).

arXiv:1709.08985•ACM Transactions on Computation Theory•Jan 28, 2021•0 citations

Certification complexity of Boolean functions

Chandrima Kayal, Sophie Laplante, Émile Larroque +2 more

Certificate complexity $(C(f ))$ is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity $(D)$ and other query models such as bounded-error randomized and quantum complexity $(R, Q)$, but not as well for quantum zero-error $(Q_0)$ and exact query complexity $(Q_E)$, where there is no agreed-upon certificate 'object' (even for $Q$). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of $C, RC$ (randomized certificate complexity) and $QC$ (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for $Q_0$, but rational degree and $Q$ are asymptotically smaller.

arXiv:2609.26757•Sep 22, 2026•0 citations

Separations in Query Complexity Based on Pointer Functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

arXiv:1506.04719•Journal of the ACM•Sep 4, 2017•28 citations

Low-Sensitivity Functions from Unambiguous Certificates

Shalev Ben-David, Pooya Hatami, Avishay Tal

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity. Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.

arXiv:1605.07084•Leibniz international proceedings in informatics•May 23, 2016•7 citations

Fractional Certificates for Bounded Functions

Shachar Lovett, Jiapeng Zhang

A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold more generally for any bounded function computed by a low degree polynomial. In this work we prove two new results towards establishing this conjecture: first, that any such polynomial has a small fractional certificate complexity; and second, that many inputs have a small sensitive block. We show that these would imply the Aaronson and Ambainis conjecture, assuming a conjectured extension of Talagrand’s concentration inequality. On the technical side, many classical techniques used in the analysis of Boolean functions seem to fail when applied to bounded functions. Here, we develop a new technique, based on a mix of combinatorics, analysis and geometry, and which in part extends a recent technique of Knop et al. (STOC 2021) to bounded functions.

Leibniz international proceedings in informatics•Jan 1, 2023•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
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 show that all known classical adversary lower bounds on randomized query complexity are equivalent for total functions and are equal to the fractional block sensitivity fbs( f ). That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. This equivalence also implies that for total functions, the relational adversary is equivalent to a simpler lower bound, which we call rank-1 relational adversary. For partial functions, we show unbounded separations between fbs( f ) and other adversary bounds, as well as between the adversary bounds themselves. We also show that, for partial functions, fractional block sensitivity cannot give lower bounds larger than √ n ⋅ bs( f ), where n is the number of variables and bs( f ) is the block sensitivity. Then, we exhibit a partial function f that matches this upper bound, fbs( f ) = Ω (√ n ⋅ bs( f )).
Certificate complexity (C(f))(C(f ))(C(f)) is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity (D)(D)(D) and other query models such as bounded-error randomized and quantum complexity (R,Q)(R, Q)(R,Q), but not as well for quantum zero-error (Q0)(Q_0)(Q0​) and exact query complexity (QE)(Q_E)(QE​), where there is no agreed-upon certificate 'object' (even for QQQ). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of C,RCC, RCC,RC (randomized certificate complexity) and QCQCQC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on QEQ_EQE​ and Q0Q_0Q0​, the quantum analogues of DDD and R0R_0R0​, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for Q0Q_0Q0​, but rational degree and QQQ are asymptotically smaller.
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.
We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.22 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity. We also show that one-sided unambiguous certificate complexity is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between block sensitivity and sensitivity. Along the way, we give a power 1.22 separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power 1.128 separation due to Goos [FOCS 2015]. As a consequence, we obtain an improved lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.
A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold more generally for any bounded function computed by a low degree polynomial. In this work we prove two new results towards establishing this conjecture: first, that any such polynomial has a small fractional certificate complexity; and second, that many inputs have a small sensitive block. We show that these would imply the Aaronson and Ambainis conjecture, assuming a conjectured extension of Talagrand’s concentration inequality. On the technical side, many classical techniques used in the analysis of Boolean functions seem to fail when applied to bounded functions. Here, we develop a new technique, based on a mix of combinatorics, analysis and geometry, and which in part extends a recent technique of Knop et al. (STOC 2021) to bounded functions.
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.