caa a22 4500 44535870X CHVBK 20180317142908.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00493-011-2580-0 doi (NATIONALLICENCE)springer-10.1007/s00493-011-2580-0 Sherstov Alexander Department of Computer Sciences, The University of Texas at Austin, 78712, Austin, TX, USA aut The unbounded-error communication complexity of symmetric functions [Elektronische Daten] [Alexander Sherstov] 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). Our proof is built around two new ideas. First, we show that a predicate D gives rise to a rapidly mixing random walk on ℤ 2 n , which allows us to reduce the problem to communication lower bounds for "typical” predicates. Second, we use Paturi's approximation lower bounds (1992), suitably generalized here to clusters of real nodes in [0,n] and interpreted in their dual form, to prove that a typical predicate behaves analogous to the parity predicate with respect to a smooth distribution on the inputs. János Bolyai Mathematical Society and Springer Verlag, 2011 Combinatorica Springer-Verlag 31/5(2011-11-01), 583-614 0209-9683 31:5<583 2011 31 493 https://doi.org/10.1007/s00493-011-2580-0 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00493-011-2580-0 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Sherstov Alexander Department of Computer Sciences, The University of Texas at Austin, 78712, Austin, TX, USA aut NATIONALLICENCE 773 0- Combinatorica Springer-Verlag 31/5(2011-11-01), 583-614 0209-9683 31:5<583 2011 31 493 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer