Please use this identifier to cite or link to this item:
Title: A composition theorem for randomized query complexity
Authors: Anshu, Anurag
Gavinsky, Dmitry
Jain, Rahul
Kundu, Srijita
Lee, Troy
Mukhopadhyay, Priyanka
Santha, Miklos
Sanyal, Swagato
Keywords: Decision Trees
Query Algorithms And Complexity
Issue Date: 2018
Source: Anshu, A., Gavinsky, D., Jain, R., Kundu, S., Lee, T., Mukhopadhyay, P., . . . Sanyal, S. (2018). A composition theorem for randomized query complexity. Leibniz International Proceedings in Informatics, 93, 10-. doi:10.4230/LIPIcs.FSTTCS.2017.10
Series/Report no.: Leibniz International Proceedings in Informatics
Abstract: 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.
DOI: 10.4230/LIPIcs.FSTTCS.2017.10
Rights: © 2018 Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal; licensed under Creative Commons License CC-BY.
Fulltext Permission: open
Fulltext Availability: With Fulltext
Appears in Collections:SPMS Journal Articles

Files in This Item:
File Description SizeFormat 
A composition theorem for randomized query complexity.pdf541.52 kBAdobe PDFThumbnail


checked on Sep 2, 2020

Page view(s)

checked on Oct 25, 2020


checked on Oct 25, 2020

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.