The unbounded-error communication complexity of symmetric functions |
| |
Authors: | Alexander A Sherstov |
| |
Institution: | 1. Department of Computer Sciences, The University of Texas at Austin, Austin, TX, 78712, USA
|
| |
Abstract: | We prove an essentially tight lower bound on the unbounded-error communication complexity of every symmetric function, i.e.,
f(x,y)=D(|x∧y|), where D: {0,1,…,n}→{0,1} is a given predicate and x,y range over {0,1}
n
. Specifically, we show that the communication complexity of f is between Θ(k/log5
n) and Θ(k logn), where k is the number of value changes of D in {0,1,…, n}. Prior to this work, the problem was solved only for the parity predicate D (Forster 2001). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|