Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-107 | 22nd June 2017 19:05

A Composition Theorem for Randomized Query complexity

RSS-Feed




Revision #1
Authors: Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
Accepted on: 22nd June 2017 19:05
Downloads: 1007
Keywords: 


Abstract:

Let the randomized query complexity of a relation for error probability \epsilon be denoted by \R_\epsilon(\cdot). We prove that for any relation f \subseteq \{0,1\}^n \times \mathcal{R} and Boolean function g:\{0,1\}^m \rightarrow \{0,1\}, \R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g)), where f \circ g^n is the relation obtained by composing f and g. We also show using an XOR lemma that \R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=\Omega(\log n \cdot \R_{4/9}(f) \cdot \R_{1/3}(g)), where g^\oplus_{O(\log n)} is the function obtained by composing the XOR function on O(\log n) bits and g.



Changes to previous version:

Corrected typos


Paper:

TR17-107 | 1st June 2017 17:39

A Composition Theorem for Randomized Query complexity


Abstract:

Let the randomized query complexity of a relation for error probability \epsilon be denoted by \R_\epsilon(\cdot). We prove that for any relation f \subseteq \{0,1\}^n \times \mathcal{R} and Boolean function g:\{0,1\}^m \rightarrow \{0,1\}, \R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g)), where f \circ g^n is the relation obtained by composing f and g. We also show that \R_{1/3}\left(f \circ \left(g^\oplus_{O(\log n)}\right)^n\right)=\Omega(\log n \cdot \R_{4/9}(f) \cdot \R_{1/3}(g)), where g^\oplus_{O(\log n)} is the function obtained by composing the xor function on O(\log n) bits and g^t.



ISSN 1433-8092 | Imprint