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
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
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).
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).
Joint computation is the ubiquitous scenario in which a computer is presented with not one, but many computational tasks to perform. A fundamental question arises: when can we cleverly combine computations, to perform them with greater efficiency or reliability than by tackling them separately? This thesis investigates the power and, especially, the limits of efficient joint computation, in several computational models: query algorithms, circuits, and Turing machines. We significantly improve and extend past results on limits to efficient joint computation for multiple independent tasks; identify barriers to progress towards better circuit lower bounds for multiple-output operators; and begin an original line of inquiry into the complexity of joint computation. In more detail, we make contributions in the following areas:
Improved product theorems for randomized query complexity: The direct product problem seeks to understand how the difficulty of computing a function on each of k independent inputs scales with k. We prove the following product theorem (DPT) for query complexity: if every T-query algorithm has success probability at most 1 – e in computing the Boolean function f on input distribution μ, then for α ≤ 1, every αeTk-query algorithm has success probability at most (2αe(1 – e))k in computing the k-fold product f ⊗k correctly on k independent inputs from μ. In light of examples due to Shaltiel, this statement gives an essentially optimal tradeoff between the query bound and the error probability. Using this DPT, we show that for an absolute constant α > 0, the worst-case success probability of any αR 2(f)k-query randomized algorithm for f⊗k falls exponentially with k. The best previous statement of this type, due to Klauck, Spalek, and de Wolf, required a query bound of O( bs(f)k).
Our proof technique involves defining and analyzing a collection of martingales associated with an algorithm attempting to solve f ⊗k. Our method is quite general and yields a new XOR lemma and threshold DPT for the query model, as well as DPTs for the query complexity of learning tasks, search problems, and tasks involving interaction with dynamic entities. We also give a version of our DPT in which decision tree size is the resource of interest.
Joint complexity in the Decision Tree Model: We study the diversity of possible behaviors of the joint computational complexity of a collection f1, …, fk of Boolean functions over a shared input. We focus on the deterministic decision tree model, with depth as the complexity measure; in this model, we prove a result to the effect that the obvious constraints on joint computational complexity are essentially the only ones.
The proof uses an intriguing new type of cryptographic data structure called a mystery bin, which we construct using a polynomial separation between deterministic and unambiguous query complexity shown by Savický. We also pose a conjecture in the communication model which, if proved, would extend our result to that model. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.) (Abstract shortened by UMI.)
We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuck and Schmeltz) that almost all Boolean functions of n arguments require Ω(n log n) queries and strengthens this bound from the worst-case over inputs to the average over inputs. The method also yields bounds for specific Boolean functions in terms of their spectra (their Fourier transforms). The simplest instance of this spectral bound yields the result (previously established by Feige, Peleg, Raghavan and Upfal) that the parity function of n arguments requires Ω(n log n) queries, and again strengthens this bound from the worst-case over inputs to the average over inputs. In its full generality, the spectral bound applies to the "highly resilient" functions introduced by Chor, Friedman, Goldreigh, Hastad, Rudich and Smolensky, and it yields non-linear lower bounds whenever the resiliency is asymptotic to the number of arguments.