TY - GEN

T1 - Interactive compression for product distributions

AU - Kol, Gillat

N1 - Funding Information:
Research supported by the National Science Foundation grant No. CCF-1412958 and the Weizmann Institute of Science National Postdoctoral Award Program for Advancing Women in Science.

PY - 2016/6/19

Y1 - 2016/6/19

N2 - We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates I2 · polylog(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.

AB - We study the interactive compression problem: Given a two-party communication protocol with small information cost, can it be compressed so that the total number of bits communicated is also small? We consider the case where the parties have inputs that are independent of each other, and give a simulation protocol that communicates I2 · polylog(I) bits, where I is the information cost of the original protocol. Our protocol is the first simulation protocol whose communication complexity is bounded by a polynomial in the information cost of the original protocol.

KW - Communication complexity

KW - Information complexity

KW - Information theory

KW - Interactive compression

UR - http://www.scopus.com/inward/record.url?scp=84979266601&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979266601&partnerID=8YFLogxK

U2 - 10.1145/2897518.2897537

DO - 10.1145/2897518.2897537

M3 - Conference contribution

AN - SCOPUS:84979266601

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 987

EP - 998

BT - STOC 2016 - Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Mansour, Yishay

A2 - Wichs, Daniel

PB - Association for Computing Machinery

T2 - 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016

Y2 - 19 June 2016 through 21 June 2016

ER -