文章基本信息
- 标题：Lifting randomized query complexity to randomized communication complexity
- 本地全文：下载
- 作者：Anurag Anshu ; Naresh Goud ; Rahul Jain 等
- 期刊名称：Electronic Colloquium on Computational Complexity
- 印刷版ISSN：1433-8092
- 出版年度：2017
- 卷号：2017
- 出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
- 摘要：
We show that for a relation f 0 1 n and a function g : 0 1 m 0 1 m 0 1 (with m = O ( log n ) ), R 1 3 ( f g n ) = R 1 3 ( f ) log 1 disc ( M g ) − O ( log n ) where f g n represents the composition of f and g n , M g is the sign matrix for g , disc ( M g ) is the discrepancy of M g under the uniform distribution and R 1 3 ( f ) ( R 1 3 ( f g n ) ) denotes the randomized query complexity of f (randomized communication complexity of f g n ) with worst case error 3 1 .
In particular, this implies that for a relation f 0 1 n , R 1 3 ( f IP n m ) = R 1 3 ( f ) m where IP m : 0 1 m 0 1 m 0 1 is the Inner Product (modulo 2 ) function and m = O ( log ( n )) .
