2017/06/01 by Anurag Anshu, Anshu, Anurag, Dmitry Gavinsky +13
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1706.00335
openalex publication_date 2017/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let the randomized query complexity of a relation for error probability ε be denoted by Rε(⋅). We prove that for any relation f ⊆ \0,1\n × R 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(log n))n)=Ω(log n ⋅ R4/9(f) ⋅ R1/3(g)), where g^⊕O(log n) is the function obtained by composing the xor function on O(log n) bits and gt.