Optimal 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_____%2F23%3A00581950" target="_blank" >RIV/67985840:_____/23:00581950 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4086/toc.2021.v017a008" target="_blank" >http://dx.doi.org/10.4086/toc.2021.v017a008</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4086/toc.2023.v019.a009" target="_blank" >10.4086/toc.2023.v019.a009</a>
Alternative languages
Result language
angličtina
Original language name
Optimal composition theorem for randomized query complexity
Original language description
For any set S, any relation F subset of {0, 1}(n) x S and any partial Boolean function, defined on a subset of {0, 1}(m), we show that R-1/3 (f o g(n)) is an element of Omega (R-4/9(f) center dot root R-1/3(g)), where R-epsilon(center dot) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g(n) subset of ({0, 1}(m))(n) x S denotes the composition of 5 with = instances of g. This result is new even in the special case when S = {0, 1} and g is a total function. We show that the new composition theorem is optimal for the general case of relations: A relation f(0) and a partial Boolean function g(0) are constructed, such that R-4/9 (f(0)) is an element of Theta(root n), R-1/3(g(0)) is an element of Theta (n) and R-1/3(f(0) o g(0)(n)) is an element of Theta (n).nThe theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by chi(center dot). Its investigation shows that (chi) over bar (g) is an element of Omega(R-1/3(g)) for any partial Boolean function g and (R-1/3(f o g(n)) is an element of Omega(R-4/9(f) center dot (chi) over bar (g)) for any relation f, which readily implies the composition statement. It is further shown that (chi) over bar (g) is always at least as large as the sabotage complexity of g (introduced by Ben-David and Kothari in 2016).
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
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
Name of the periodical
Theory of Computing
ISSN
1557-2862
e-ISSN
1557-2862
Volume of the periodical
19
Issue of the periodical within the volume
December
Country of publishing house
US - UNITED STATES
Number of pages
35
Pages from-to
9
UT code for WoS article
001137473500001
EID of the result in the Scopus database
—