Paper Info
Title
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract
Abstract
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of partial Boolean functions f and g such that R(f°g) ≪ R(f)R(g). In fact, we show that the left hand side can be polynomially smaller than the right hand side (though in our construction, both sides are polylogarithmic in the input size of f). Second, we show that for all f and g, R(f°g) = Ω(noisyR(f) R(g)), where noisyR(f) is a measure describing the cost of computing f on noisy oracle inputs. We show that this composition theorem is the strongest possible of its type: for any measure M(·) satisfying R(f°g)=Ω(M(f)R(g)) for all f and g, it must hold that noisyR(f)=Ω(M(f)) for all f. We also give a clean characterization of the measure noisyR(f): it satisfies noisyR(f)=Θ(R(f°GapMajn)/R(GapMajn)), where n is the input size of f and GapMajn is the √n-gap majority function on n bits.
Year
DOI
Venue
2020
10.1109/FOCS46700.2020.00031
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
Keywords
DocType
ISSN
Query complexity,Randomized computation,Function composition,Noisy oracle,Gap Majority function
Conference
1523-8288
ISBN
Citations 
PageRank 
978-1-7281-9622-0
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Shalev Ben-David1638.92
Eric Blais228622.49