Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DECISION TREE COMPLEXITY:
Reports tagged with decision tree complexity:
TR02-002 | 3rd January 2002
Howard Barnum, Michael Saks

A lower bound on the quantum query complexity of read-once functions

We establish a lower bound of $\Omega{(\sqrt{n})}$ on the bounded-error quantum query complexity of read-once Boolean functions, providing evidence for the conjecture that $\Omega(\sqrt{D(f)})$ is a lower bound for all Boolean functions.Our technique extends a result of Ambainis, based on the idea that successful computation of a function requires decoherence'' ... more >>>

TR08-096 | 8th September 2008
Andrew Drucker

Multitask Efficiencies in the Decision Tree Model

In Direct Sum problems [KRW], one tries to show that for a given computational model, the complexity of computing a collection $F = \{f_1(x_1), \ldots f_l(x_l)\}$ of finite functions on independent inputs is approximately the sum of their individual complexities. In this paper, by contrast, we study the diversity of ... more >>>

TR12-063 | 17th May 2012
Raghav Kulkarni, Miklos Santha

Query complexity of matroids

Let $\mathcal{M}$ be a bridgeless matroid on ground set $\{1,\ldots, n\}$ and $f_{\mathcal{M}}: \{0,1\}^n \to \{0, 1\}$ be the indicator function of its independent sets. A folklore fact is that $f_\mathcal{M}$ is evasive," i.e., $D(f_\mathcal{M}) = n$ where $D(f)$ denotes the deterministic decision tree complexity of $f.$ Here we prove ... more >>>

TR12-099 | 5th August 2012
Nikos Leonardos

An improved lower bound for the randomized decision tree complexity of recursive majority

Revisions: 1

We prove that the randomized decision tree complexity of the recursive majority-of-three is $\Omega(2.6^d)$, where $d$ is the depth of the recursion. The proof is by a bottom up induction, which is same in spirit as the one in the proof of Saks and Wigderson in their FOCS 1986 paper ... more >>>

TR14-061 | 21st April 2014
Raghav Kulkarni, Youming Qiao, Xiaoming Sun

Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive

For a Boolean function $f,$ let $D(f)$ denote its deterministic decision tree complexity, i.e., minimum number of (adaptive) queries required in worst case in order to determine $f.$ In a classic paper,
Rivest and Vuillemin \cite{rv} show that any non-constant monotone property $\mathcal{P} : \{0, 1\}^{n \choose 2} \to ... more >>> TR15-108 | 30th June 2015 Shalev Ben-David A Super-Grover Separation Between Randomized and Quantum Query Complexities We construct a total Boolean function$f$satisfying$R(f)=\tilde{\Omega}(Q(f)^{5/2})$, refuting the long-standing conjecture that$R(f)=O(Q(f)^2)$for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to$R(f)=\tilde{\Omega}(Q(f)^3)$. Our construction is motivated by the Göös-Pitassi-Watson function but does not ... more >>> TR15-175 | 5th November 2015 Scott Aaronson, Shalev Ben-David, Robin Kothari Separations in query complexity using cheat sheets We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity ... more >>> TR15-203 | 13th December 2015 Scott Aaronson, Shalev Ben-David Sculpting Quantum Speedups Given a problem which is intractable for both quantum and classical algorithms, can we find a sub-problem for which quantum algorithms provide an exponential advantage? We refer to this problem as the "sculpting problem." In this work, we give a full characterization of sculptable functions in the query complexity setting. ... more >>> TR16-084 | 23rd May 2016 Shalev Ben-David Low-Sensitivity Functions from Unambiguous Certificates 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.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a ... more >>> TR16-087 | 30th May 2016 Shalev Ben-David, Robin Kothari Randomized query complexity of sabotaged and composed functions We study the composition question for bounded-error randomized query complexity: Is R(f o g) = Omega(R(f) R(g)) for all Boolean functions f and g? We show that inserting a simple Boolean function h, whose query complexity is only Theta(log R(g)), in between f and g allows us to prove R(f ... more >>> TR17-029 | 18th February 2017 Clement Canonne, Tom Gur An Adaptivity Hierarchy Theorem for Property Testing Revisions: 1 Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of \emph{adaptive} testing algorithms, wherein each query may be determined by the answers received to prior queries, and their \emph{non-adaptive} counterparts, in which all ... more >>> TR17-191 | 15th December 2017 Alexander Smal, Navid Talebanfard Prediction from Partial Information and Hindsight, an Alternative Proof Revisions: 2 Let$X$be a random variable distributed over$n$-bit strings with$H(X) \ge n - k$, where$k \ll n$. Using subadditivity we know that a random coordinate looks random. Meir and Wigderson [TR17-149] showed a random coordinate looks random to an adversary who is allowed to query around$n/k\$ ... more >>>

ISSN 1433-8092 | Imprint