Skip to main content

New separations results for external information

Author(s): Braverman, Mark; Minzer, Dor

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1mz7f
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorMinzer, Dor-
dc.date.accessioned2021-10-08T19:50:51Z-
dc.date.available2021-10-08T19:50:51Z-
dc.date.issued2021en_US
dc.identifier.citationBraverman, Mark, and Dor Minzer. "New separations results for external information." In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021): pp. 248-258. doi:10.1145/3406325.3451044en_US
dc.identifier.urihttps://arxiv.org/pdf/2103.04049.pdf-
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1mz7f-
dc.description.abstractWe obtain new separation results for the two-party external information complexity of Boolean functions. The external information complexity of a function f(x,y) is the minimum amount of information a two-party protocol computing f must reveal to an outside observer about the input. We prove an exponential separation between external and internal information complexity, which is the best possible; previously no separation was known. We use this result in order to then prove a near-quadratic separation between amortized zero-error communication complexity and external information complexity for total functions, disproving a conjecture of the first author. Finally, we prove a matching upper bound showing that our separation result is tight.en_US
dc.format.extent248 - 258en_US
dc.language.isoen_USen_US
dc.relation.ispartofProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computingen_US
dc.rightsAuthor's manuscripten_US
dc.titleNew separations results for external informationen_US
dc.typeConference Articleen_US
dc.identifier.doi10.1145/3406325.3451044-
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/conference-proceedingen_US

Files in This Item:
File Description SizeFormat 
NewSeparationResults.pdf357.64 kBAdobe PDFView/Download


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