2026-07-24T00:04:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8396 2024-03-06T10:41:56Z ddc:004 open_access

A Composition Theorem for Randomized Query Complexity Anshu, Anurag Gavinsky, Dmitry Jain, Rahul Kundu, Srijita Lee, Troy Mukhopadhyay, Priyanka Santha, Miklos Sanyal, Swagato Query algorithms and complexity Decision trees Composition theorem XOR lemma Hardness amplification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anurag Anshu and Dmitry Gavinsky and Rahul Jain and Srijita Kundu and Troy Lee and Priyanka Mukhopadhyay and Miklos Santha and Swagato Sanyal 2018 Is Part Of LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2017.10 urn:nbn:de:0030-drops-83967 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.10 eng https://creativecommons.org/licenses/by/3.0/legalcode