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 -