Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOMIZED QUERY COMPLEXITY:
Reports tagged with randomized query complexity:
TR11-033 | 8th March 2011
Rahul Jain, Shengyu Zhang

The influence lower bound via query elimination

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function $f$ in terms of the maximum influence of any variable of $f$. Our lower bound also applies to ... more >>>


TR17-054 | 22nd March 2017
Anurag Anshu, Naresh Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

Lifting randomized query complexity to randomized communication complexity

Revisions: 4

We show that for any (partial) query function $f:\{0,1\}^n\rightarrow \{0,1\}$, the randomized communication complexity of $f$ composed with $\mathrm{Index}^n_m$ (with $m= \poly(n)$) is at least the randomized query complexity of $f$ times $\log n$. Here $\mathrm{Index}_m : [m] \times \{0,1\}^m \rightarrow \{0,1\}$ is defined as $\mathrm{Index}_m(x,y)= y_x$ (the $x$th bit ... more >>>


TR17-150 | 26th September 2017
Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs

All Classical Adversary Methods are Equivalent for Total Functions

Revisions: 2

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 $\text{fbs}(f)$. That includes the Kolmogorov complexity bound of Laplante and Magniez and the earlier relational adversary bound of Aaronson. For partial functions, we show ... more >>>


TR20-128 | 3rd September 2020
Alexander A. Sherstov, Andrey Storozhenko, Pei Wu

An Optimal Separation of Randomized and Quantum Query Complexity

Revisions: 1

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order $\ell\geq1$ sum to at most $c^{\ell}\sqrt{{d\choose\ell}(1+\log n)^{\ell-1}},$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant. This bound is essentially tight and settles a ... more >>>


TR23-099 | 8th July 2023
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh

On the Composition of Randomized Query Complexity and Approximate Degree

Revisions: 1

For any Boolean functions $f$ and $g$, the question whether $\text{R}(f\circ g) = \tilde{\Theta}(\text{R}(f) \cdot \text{R}(g))$, is known as the composition question for the randomized query complexity. Similarly, the composition question for the approximate degree asks whether $\widetilde{\text{deg}}(f\circ g) = \tilde{\Theta}(\widetilde{\text{deg}}(f)\cdot\widetilde{\text{deg}}(g))$. These questions are two of the most important and ... more >>>


TR24-016 | 27th January 2024
Swagato Sanyal

Randomized query composition and product distributions

Let R_eps denote randomized query complexity for error probability eps, and R:=R_{1/3}. In this work we investigate whether a perfect composition theorem R(f o g^n)=Omega(R(f).R(g)) holds for a relation f in {0,1}^n * S and a total inner function g:{0,1}^m \to {0, 1}.

Let D^(prod) denote the maximum distributional query ... more >>>




ISSN 1433-8092 | Imprint