Optimal composition theorem for randomized query complexity

0581950 - MÚ 2024 RIV US eng J - Journal Article
Gavinsky, Dmitry - Lee, T. - Santha, M. - Sanyal, S.
Optimal composition theorem for randomized query complexity.
Theory of Computing. Roč. 19, December (2023), č. článku 9. ISSN 1557-2862. E-ISSN 1557-2862
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : query complexity * randomized decision tree * composed function * lower bound
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 1, year: 2022
Method of publishing: Open access
http://dx.doi.org/10.4086/toc.2021.v017a008

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).
The 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).
Permanent Link: https://hdl.handle.net/11104/0350086