A composition theorem for randomized query complexity via Max-conflict complexity

0507748 - MÚ 2020 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Gavinsky, Dmitry - Lee, T. - Santha, M. - Sanyal, S.
A composition theorem for randomized query complexity via Max-conflict complexity.
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2019 - (Baier, C.; Chatzigiannakis, I.; Flocchini, P.; Leonardi, S.), č. článku 64. Leibniz International Proceedings in Informatics (LIPIcs), 132. ISBN 978-3-95977-109-2. ISSN 1868-8969.
[46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Patras (GR), 08.07.2019-12.07.2019]
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: query complexity * lower bounds
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
http://drops.dagstuhl.de/opus/volltexte/2019/10640/

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 bounded-error 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, max-conflict 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.
Trvalý link: http://hdl.handle.net/11104/0298723