2017/03/22 by Anshu, Anurag, Goud, Naresh B., Jain, Rahul +2
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1703.07521
We show that for a relation f⊆ \0,1\n× O and a function g:\0,1\m× \0,1\m → \0,1\ (with m= O(log n)), R1/3(f∘ gn) = Ω(R1/3(f) ⋅ (log(1)/(disc(Mg)) - O(log n))), where f∘ gn represents the composition of f and gn, Mg is the sign matrix for g, disc(Mg) is the discrepancy of Mg under the uniform distribution and R1/3(f) (R1/3(f∘ gn)) denotes the randomized query complexity of f (randomized communication complexity of f∘ gn) with worst case error (1)/(3). In particular, this implies that for a relation f⊆ \0,1\n× O, R1/3(f∘ IPmn) = Ω(R1/3(f) ⋅ m), where IPm:\0,1\m× \0,1\m→ \0,1\ is the Inner Product (modulo 2) function and m= O(log(n)).