TY - GEN

T1 - New separations results for external information

AU - Braverman, Mark

AU - Minzer, Dor

N1 - Funding Information:
∗Research supported in part by the NSF Alan T. Waterman Award, Grant No. 1933331, a Packard Fellowship in Science and Engineering, and the Simons Collaboration on Algorithms and Geometry. 1See Section 2 for rigorous definitions and further background.
Publisher Copyright:
© 2021 ACM.

PY - 2021/6/15

Y1 - 2021/6/15

N2 - 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.

AB - 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.

KW - Communication Complexity

KW - Information Complexity

UR - http://www.scopus.com/inward/record.url?scp=85108164979&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85108164979&partnerID=8YFLogxK

U2 - 10.1145/3406325.3451044

DO - 10.1145/3406325.3451044

M3 - Conference contribution

AN - SCOPUS:85108164979

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 248

EP - 258

BT - STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Khuller, Samir

A2 - Williams, Virginia Vassilevska

PB - Association for Computing Machinery

T2 - 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021

Y2 - 21 June 2021 through 25 June 2021

ER -