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
Abstract: We 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.
Publication Date: 2021
Citation: Braverman, 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.3451044
DOI: 10.1145/3406325.3451044
Pages: 248 - 258
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Version: Author's manuscript



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