A composition theorem for randomized query complexity

0487435 - MÚ 2018 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Anshu, A. - Gavinsky, Dmitry - Jain, R. - Kundu, S. - Lee, T. - Mukhopadhyay, P. - Santha, M. - Sanyal, S.
A composition theorem for randomized query complexity.
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Dagstuhl: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2018 - (Lokam, S.; Ramanujam, R.), s. 1-13, č. článku 10. Leibniz International Proceedings in Informatics, 93. ISBN 978-3-95977-055-2. ISSN 1868-8969.
[37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Kanpur (IN), 11.12.2017-15.12.2017]
Grant CEP: GA ČR GBP202/12/G061
Institucionální podpora: RVO:67985840
Klíčová slova: query algorithms and complexity * decision trees * composition theorem
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/2018/8396/

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.
Trvalý link: http://hdl.handle.net/11104/0282096