A composition theorem for randomized query complexity

Publication date 25 November 2020

Abstract: Let the randomized query complexity of a relation for error probability

e p s i l o n

be denoted by

R_{e} p s i l o n (c d o t)

. We prove that for any relation

f s u b s e t e q {0, 1}^{n} i m e s m a t h c a l R

and Boolean function

g : {0, 1}^{m} i g h t a r r o w 0, 1

,

R_{1 / 3} (f c i r c g^{n}) = O m e g a (R_{4 / 9} (f) c d o t R_{1 / 2 - 1 / n^{4}} (g))

, where

f c i r c g^{n}

is the relation obtained by composing

f

and

g

. We also show that

R_{1 / 3} l e f t (f c i r c l e f t (g^{o} p l u s_{O (l o g n)} i g h t)^{n} i g h t) = O m e g a (l o g n c d o t R_{4 / 9} (f) c d o t R_{1 / 3} (g))

, where

g^{o} p l u s_{O (l o g n)}

is the function obtained by composing the xor function on

O (l o g n)

bits and

g^{t}

.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: A composition theorem for randomized query complexity