2026-07-22T16:01:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10640 2024-03-06T10:46:21Z ddc:004 open_access

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity Gavinsky, Dmitry Lee, Troy Santha, Miklos Sanyal, Swagato query complexity lower bounds For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Gavinsky and Troy Lee and Miklos Santha and Swagato Sanyal 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.64 urn:nbn:de:0030-drops-106407 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.64 eng https://creativecommons.org/licenses/by/3.0/legalcode