Gavinsky, Dmitry ;
Lee, Troy ;
Santha, Miklos ;
Sanyal, Swagato
A Composition Theorem for Randomized Query Complexity via MaxConflict Complexity
Abstract
For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m > {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the boundederror randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g.
The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n).
The theorem is proved via introducing a new complexity measure, maxconflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.
BibTeX  Entry
@InProceedings{gavinsky_et_al:LIPIcs:2019:10640,
author = {Dmitry Gavinsky and Troy Lee and Miklos Santha and Swagato Sanyal},
title = {{A Composition Theorem for Randomized Query Complexity via MaxConflict Complexity}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {64:164:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10640},
URN = {urn:nbn:de:0030drops106407},
doi = {10.4230/LIPIcs.ICALP.2019.64},
annote = {Keywords: query complexity, lower bounds}
}
04.07.2019
Keywords: 

query complexity, lower bounds 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 