A composition theorem for randomized query complexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F18%3A00487435" target="_blank" >RIV/67985840:_____/18:00487435 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.10" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.10</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2017.10" target="_blank" >10.4230/LIPIcs.FSTTCS.2017.10</a>
Alternative languages
Result language
angličtina
Original language name
A composition theorem for randomized query complexity
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
ISBN
978-3-95977-055-2
ISSN
1868-8969
e-ISSN
—
Number of pages
13
Pages from-to
—
Publisher name
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Place of publication
Dagstuhl
Event location
Kanpur
Event date
Dec 11, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—