Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND

68 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “The following lemma, due to [23], allows us to relate dH ( pY n z ,p Y n z⊕i ) , the distance between message distributions when all players get observations from pz , or all from pz⊕i , to the distances dH ( pY n z ,p Y n t←z⊕i ) where only one of the n players gets a sample from pz⊕i .”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, background): “Every t -pass algorithm designed for turnstile streams requires Ω( n 1 − 2 /p /t ) bits, which follows by injecting the F p -moment problem (see (Gronemeier, 2009; Jayram, 2009)) into the diagonal elements.”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, background): “It is known ( [3, 9, 12, 18, 19, 25]) that the following problem needs Ω(n) bits of communication even for a randomized algorithm: we distinguish between two situations: (a) Each of s servers holds a subset of [n] and the subsets are pairwise disjoint and (b) There is exactly one element common to a”