Skip to main content

Interactive Information Complexity

Author(s): Braverman, Mark

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr10v58
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.date.accessioned2021-10-08T19:44:55Z-
dc.date.available2021-10-08T19:44:55Z-
dc.date.issued2015en_US
dc.identifier.citationBraverman, Mark. "Interactive Information Complexity." SIAM Journal on Computing 44, no. 6 (2015): 1698-1739. doi:10.1137/130938517en_US
dc.identifier.issn0097-5397-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr10v58-
dc.description.abstractThe primary goal of this paper is to define and study the interactive information complexity of functions. Let f(x, y) be a function, and suppose Alice is given x and Bob is given y. Informally, the interactive information complexity IC(f) of f is the least amount of information Alice and Bob need to reveal to each other to compute f. Previously, information complexity has been defined with respect to a prior distribution on the input pairs (x, y). Our first goal is to give a definition that is independent of the prior distribution. We show that several possible definitions are essentially equivalent. We establish some basic properties of the interactive information complexity IC(f). In particular, we show that IC(f) is equal to the amortized (randomized) communication complexity of f. We also show a direct sum theorem for IC(f) and give the first general connection between information complexity and (nonamortized) communication complexity. This connection implies that a nontrivial exchange of information is required when solving problems that have nontrivial communication complexity. We explore the information complexity of two specific problems: Equality and Disjointness. We show that only a constant amount of information needs to be exchanged when solving equality with no errors, while solving disjointness with a constant error probability requires the parties to reveal a linear amount of information to each other.en_US
dc.format.extent1698 - 1739en_US
dc.language.isoen_USen_US
dc.relation.ispartofSIAM Journal on Computingen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleInteractive Information Complexityen_US
dc.typeJournal Articleen_US
dc.identifier.doi10.1137/130938517-
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 
InteractiveInformationComplexitysiam.pdf429 kBAdobe PDFView/Download


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