To refer to this page use:
|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.|
|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|
|Pages:||248 - 258|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.