View Related Documents

Abstract

The AND{\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 (YES{\textsc{Yes}} instance). In this note, I will give a new proof of an Ω(1/t) lower bound on the information complexity of AND{\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 .

Fulltext Preview

Image of the first page of the fulltext document