Skip to main content

How to Compress Interactive Communication

Author(s): Barak, Boaz; Braverman, Mark; Chen, Xi; Rao, Anup

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1mn9v
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBarak, Boaz-
dc.contributor.authorBraverman, Mark-
dc.contributor.authorChen, Xi-
dc.contributor.authorRao, Anup-
dc.date.accessioned2021-10-08T19:44:56Z-
dc.date.available2021-10-08T19:44:56Z-
dc.date.issued2013en_US
dc.identifier.citationBarak, Boaz, Mark Braverman, Xi Chen, and Anup Rao. "How to Compress Interactive Communication." SIAM Journal on Computing 42, no. 3 (2013): 1327-1363. doi:10.1137/100811969en_US
dc.identifier.issn0097-5397-
dc.identifier.urihttps://www.cs.princeton.edu/~mbraverm/pmwiki/uploads/directsum.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1mn9v-
dc.description.abstractWe describe new ways to simulate two-party communication protocols to get protocols with potentially less communication. We show that every communication protocol that communicates C bits and reveals I bits of information about the inputs to the participating parties can be simulated by a new protocol involving at most O˜( √CI) bits of communication. If the protocol reveals I bits of information about the inputs to an observer that watches the communication in the protocol, we show how to carry out the simulation with O˜(I) bits of communication. These results lead to a direct sum theorem for randomized communication complexity. Ignoring polylogarithmic factors, we show that for worst-case computation, computing n copies of a function requires √n times the communication required for computing one copy of the function. For average case complexity, given any distribution μ on inputs, computing n copies of the function on n inputs sampled independently according to μ requires √n times the communication for computing one copy. If μ is a product distribution, computing n copies on n independent inputs sampled according to μ requires n times the communication required for computing the function. We also study the complexity of computing the sum (or parity) of n evaluations of f, and obtain results analogous to those above. Our results give the first compression schemes for general randomized protocols and the first direct sum results in the general setting of randomized and distributional communication complexity, without requiring bound on the number of rounds in the protocol or that the distribution of inputs is independent.en_US
dc.format.extent1327 - 1363en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleHow to Compress Interactive Communicationen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1137/100811969-
dc.identifier.eissn1095-7111-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
CompressInteractiveCommunication.pdf380.46 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.