New separations results for external information

Mark Braverman; Dor Minzer

doi:10.1145/3406325.3451044

New separations results for external information

Mark Braverman, Dor Minzer

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
Editors	Samir Khuller, Virginia Vassilevska Williams
Publisher	Association for Computing Machinery
Pages	248-258
Number of pages	11
ISBN (Electronic)	9781450380539
DOIs	https://doi.org/10.1145/3406325.3451044
State	Published - Jun 15 2021
Event	53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy Duration: Jun 21 2021 → Jun 25 2021

Publication series

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

Conference

Conference	53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021
Country/Territory	Italy
City	Virtual, Online
Period	6/21/21 → 6/25/21

All Science Journal Classification (ASJC) codes

Software

Keywords

Communication Complexity
Information Complexity

Access to Document

10.1145/3406325.3451044

Cite this

Braverman, M., & Minzer, D. (2021). New separations results for external information. In S. Khuller, & V. V. Williams (Eds.), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (pp. 248-258). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3406325.3451044

@inproceedings{4509ce5c2466458a8aae676dfc890419,

title = "New separations results for external information",

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.",

keywords = "Communication Complexity, Information Complexity",

author = "Mark Braverman and Dor Minzer",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 ; Conference date: 21-06-2021 Through 25-06-2021",

year = "2021",

month = jun,

day = "15",

doi = "10.1145/3406325.3451044",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "248--258",

editor = "Samir Khuller and Williams, {Virginia Vassilevska}",

booktitle = "STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing",

}

Braverman, M & Minzer, D 2021, New separations results for external information. in S Khuller & VV Williams (eds), STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 248-258, 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021, Virtual, Online, Italy, 6/21/21. https://doi.org/10.1145/3406325.3451044

New separations results for external information. / Braverman, Mark; Minzer, Dor.
STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ed. / Samir Khuller; Virginia Vassilevska Williams. Association for Computing Machinery, 2021. p. 248-258 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - New separations results for external information

AU - Braverman, Mark

AU - Minzer, Dor

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 -

New separations results for external information

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this