Anshu, AnuragGavinsky, DmitryJain, RahulKundu, SrijitaLee, TroyMukhopadhyay, PriyankaSantha, MiklosSanyal, Swagato2024-04-172017-06-14Anshu, Anurag, Dmiry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. "A Composition Theorem for Randomized Query Complexity." Pre-print, 2017.https://nrs.harvard.edu/URN-3:HUL.INSTREPOS:37378353Let the randomized query complexity of a relation for error probability ϵ be denoted by Rϵ(⋅). We prove that for any relation f⊆{0,1}n× and Boolean function g:{0,1}m→{0,1}, R1/3(f∘gn)=Ω(R4/9(f)⋅R1/2−1/n4(g)), where f∘gn is the relation obtained by composing f and g. We also show that R1/3(f∘(g⊕O(logn))n)=Ω(logn⋅R4/9(f)⋅R1/3(g)), where g⊕O(logn) is the function obtained by composing the xor function on O(logn) bits and gt.en-USJournal Article2024-04-17