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

Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions

Nikos Leonardos

Published Dec 10, 2022• 0 citations
Publisher

Abstract

Abstract: In this work we prove lower bounds on the randomized decision tree complexity of several read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, in which every internal node is labeled by a threshold function (with output 1 only when at least out of input bits are 1) and each leaf by a variable. We consider the randomized decision tree complexity of such functions, when the underlying tree is a uniform and balanced tree with all its internal nodes labeled by the same threshold function. We prove lower bounds of the form , where is the depth of the tree, for certain values of and. The value of each parameter depends on the solution of a linear program, which is provided by computational methods. Keywords: Decision trees, query complexity, randomized computation, lower bounds, read-once functions. Title: Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions Author: Nikos Leonardos International Journal of Recent Research in Mathematics Computer Science and Information Technology ISSN 2350-1022 Vol. 9, Issue 2, October 2022 - March 2023 Page No: 11-17 Paper Publications Website: www.paperpublications.org Published Date: 10-December-2022 DOI: https://doi.org/10.5281/zenodo.7421269 Paper Download Link (Source) https://www.paperpublications.org/upload/book/Computer-assisted%20proof%20of%20lower-10122022-1.pdf

DOI
10.5281/zenodo.7421268

Related papers

Decision Trees and Branching Programs

Thomas Watson

This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.

Cambridge University Press eBooks•Oct 9, 2026•0 citations

Entropy lower bounds of quantum decision tree complexity

Yaoyun Shi

We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log(n)) bits. Let E(f) be the Shannon entropy of the random variable f(X), where X is uniformly random in f's domain. Our main result is that it takes Ω(E(f)) queries to compute any \emph{total} function f. It is interesting to contrast this bound with the Ω(E(f)/log(n)) bound, which is tight for \emph{partial} functions. Our approach is the polynomial method.

arXiv:quant-ph/0008095•Aug 23, 2000•1 citation

An Optimal Separation of Randomized and Quantum Query Complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).

arXiv:2008.10223•SIAM Journal on Computing•Apr 26, 2023•23 citations

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture

Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif

We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).

Leibniz international proceedings in informatics•Jan 1, 2021•5 citations

Separating Decision Tree Complexity from Subcube Partition Complexity

Robin Kothari, David Racicot-Desloges, Miklós Sántha

The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose deterministic subcube partition complexity is asymptotically smaller than its randomized decision tree complexity, resolving an open problem of Friedgut, Kahn, and Wigderson (2002). Our lower bound is based on the information-theoretic techniques first introduced to lower bound the randomized decision tree complexity of the recursive majority function. We also show that the public-coin partition bound, the best known lower bound method for randomized decision tree complexity subsuming other general techniques such as block sensitivity, approximate degree, randomized certificate complexity, and the classical adversary bound, also lower bounds randomized subcube partition complexity. This shows that all these lower bound techniques cannot prove optimal lower bounds for randomized decision tree complexity, which answers an open question of Jain and Klauck (2010) and Jain, Lee, and Vishnoi (2014).

arXiv:1504.01339•Leibniz international proceedings in informatics•Jan 1, 2015•10 citations

The Information Complexity of Decision Trees

Avantika Agarwal, Shalev Ben-David, Eric Blais

We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).

arXiv:2609.12164•Sep 10, 2026•0 citations
Abstract: In this work we prove lower bounds on the randomized decision tree complexity of several read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, in which every internal node is labeled by a threshold function (with output 1 only when at least out of input bits are 1) and each leaf by a variable. We consider the randomized decision tree complexity of such functions, when the underlying tree is a uniform and balanced tree with all its internal nodes labeled by the same threshold function. We prove lower bounds of the form , where is the depth of the tree, for certain values of and. The value of each parameter depends on the solution of a linear program, which is provided by computational methods. Keywords: Decision trees, query complexity, randomized computation, lower bounds, read-once functions. Title: Computer-assisted proof of lower bounds on the randomized query complexity of certain read-once threshold functions Author: Nikos Leonardos International Journal of Recent Research in Mathematics Computer Science and Information Technology ISSN 2350-1022 Vol. 9, Issue 2, October 2022 - March 2023 Page No: 11-17 Paper Publications Website: www.paperpublications.org Published Date: 10-December-2022 DOI: https://doi.org/10.5281/zenodo.7421269 Paper Download Link (Source) https://www.paperpublications.org/upload/book/Computer-assisted%20proof%20of%20lower-10122022-1.pdf
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.
We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log(n)) bits. Let E(f) be the Shannon entropy of the random variable f(X), where X is uniformly random in f's domain. Our main result is that it takes Ω(E(f)) queries to compute any \emph{total} function f. It is interesting to contrast this bound with the Ω(E(f)/log(n)) bound, which is tight for \emph{partial} functions. Our approach is the polynomial method.
Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on n input bits, each of which has approximate Fourier sparsity at most O(n³) and randomized parity decision tree complexity Θ(n). This improves upon the recent work of Chattopadhyay, Mande and Sherif [Chattopadhyay et al., 2020] both qualitatively (in terms of designing a large number of examples) and quantitatively (shrinking the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
The subcube partition model of computation is at least as powerful as decision trees but no separation between these models was known. We show that there exists a function whose deterministic subcube partition complexity is asymptotically smaller than its randomized decision tree complexity, resolving an open problem of Friedgut, Kahn, and Wigderson (2002). Our lower bound is based on the information-theoretic techniques first introduced to lower bound the randomized decision tree complexity of the recursive majority function. We also show that the public-coin partition bound, the best known lower bound method for randomized decision tree complexity subsuming other general techniques such as block sensitivity, approximate degree, randomized certificate complexity, and the classical adversary bound, also lower bounds randomized subcube partition complexity. This shows that all these lower bound techniques cannot prove optimal lower bounds for randomized decision tree complexity, which answers an open question of Jain and Klauck (2010) and Jain, Lee, and Vishnoi (2014).
We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).