Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MARCO MOLINARO:
All reports by Author Marco Molinaro:

TR15-031 | 2nd March 2015
Marco Molinaro, David Woodruff, Grigory Yaroslavtsev

Amplification of One-Way Information Complexity via Codes and Noise Sensitivity

Revisions: 1

We show a new connection between the information complexity of one-way communication problems under product distributions and a relaxed notion of list-decodable codes. As a consequence, we obtain a characterization of the information complexity of one-way problems under product distributions for any error rate based on covering numbers. This generalizes ... more >>>




ISSN 1433-8092 | Imprint