Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SAGAR KALE:
All reports by Author Sagar Kale:

TR16-111 | 20th July 2016
Amit Chakrabarti, Sagar Kale

Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics

We develop a paradigm for studying multi-player deterministic communication,
based on a novel combinatorial concept that we call a {\em strong fooling
set}. Our paradigm leads to optimal lower bounds on the per-player
communication required for solving multi-player $\textsc{equality}$
problems in a private-message setting. This in turn gives a ... more >>>




ISSN 1433-8092 | Imprint