Počet záznamů: 1
A composition theorem for randomized query complexity
- 1.
SYSNO ASEP 0487435 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název A composition theorem for randomized query complexity Tvůrce(i) Anshu, A. (SG)
Gavinsky, Dmitry (MU-W) RID, SAI, ORCID
Jain, R. (SG)
Kundu, S. (SG)
Lee, T. (SG)
Mukhopadhyay, P. (SG)
Santha, M. (SG)
Sanyal, S. (SG)Číslo článku 10 Zdroj.dok. 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. - ISSN 1868-8969 - ISBN 978-3-95977-055-2 Rozsah stran s. 1-13 Poč.str. 13 s. Forma vydání Online - E Akce 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) Datum konání 11.12.2017 - 15.12.2017 Místo konání Kanpur Země IN - Indie Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova query algorithms and complexity ; decision trees ; composition theorem Vědní obor RIV BA - Obecná matematika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GBP202/12/G061 GA ČR - Grantová agentura ČR Institucionální podpora MU-W - RVO:67985840 EID SCOPUS 85043986619 DOI 10.4230/LIPIcs.FSTTCS.2017.10 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2018
Počet záznamů: 1