Paper Info
Title
Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
Abstract
The ${\textsc{And}}$ problem on t bits is a promise decision problem where either at most one bit of the input is set to 1 (No instance) or all t bits are set to 1 (${\textsc{Yes}}$ instance). In this note, I will give a new proof of an ***(1/t ) lower bound on the information complexity of ${\textsc{And}}$ in the number-in-hand model of communication. This was recently established by Gronemeier, STACS 2009. The proof exploits the information geometry of communication protocols via Hellinger distance in a novel manner and avoids the analytic approach inherent in previous work. As previously known, this bound implies an ***(n /t ) lower bound on the communication complexity of multiparty disjointness and consequently a ***(n 1 *** 2/k ) space lower bound on estimating the k -th frequency moment F k .
Year
DOI
Venue
2009
10.1007/978-3-642-03685-9_42
APPROX-RANDOM
Keywords
Field
DocType
hellinger distance,multi-party information complexity,communication protocol,analytic approach,information complexity,novel manner,multiparty disjointness,new proof,hellinger strikes,promise decision problem,communication complexity,information geometry,decision problem,lower bound
Discrete mathematics,Information geometry,Decision problem,Combinatorics,Hellinger distance,Upper and lower bounds,Models of communication,Communication complexity,Information complexity,Mathematics,Communications protocol
Conference
Volume
ISSN
Citations 
5687
0302-9743
28
PageRank 
References 
Authors
1.07
17
1
Name
Order
Citations
PageRank
T. S. Jayram1137375.87