New separations results for external information

Mark Braverman, Dor Minzer

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationSTOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
EditorsSamir Khuller, Virginia Vassilevska Williams
PublisherAssociation for Computing Machinery
Number of pages11
ISBN (Electronic)9781450380539
StatePublished - Jun 15 2021
Event53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy
Duration: Jun 21 2021Jun 25 2021

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
CityVirtual, Online

All Science Journal Classification (ASJC) codes

  • Software


  • Communication Complexity
  • Information Complexity


Dive into the research topics of 'New separations results for external information'. Together they form a unique fingerprint.

Cite this