A composition theorem for randomized query complexity

A composition theorem for randomized query complexity

Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation ob...

Full description

Saved in:
Bibliographic Details
Main Authors: Anshu, Anurag, Gavinsky, Dmitry, Jain, Rahul, Kundu, Srijita, Lee, Troy, Mukhopadhyay, Priyanka, Santha, Miklos, Sanyal, Swagato
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2018
Subjects:
Decision Trees
DRNTU::Science::Mathematics
Query Algorithms And Complexity
Online Access:https://hdl.handle.net/10356/89383
http://hdl.handle.net/10220/46216
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:Let the randomized query complexity of a relation for error probability epsilon be denoted by R_epsilon(). We prove that for any relation f contained in {0,1}^n times R and Boolean function g:{0,1}^m -> {0,1}, R_{1/3}(f o g^n) = Omega(R_{4/9}(f).R_{1/2-1/n^4}(g)), where f o g^n is the relation obtained by composing f and g. We also show using an XOR lemma that R_{1/3}(f o (g^{xor}_{O(log n)})^n) = Omega(log n . R_{4/9}(f) . R_{1/3}(g))$, where g^{xor}_{O(log n)} is the function obtained by composing the XOR function on O(log n) bits and g.

Similar Items