Exponential separation of information and communication

Anat Ganor; Gillat Kol; Ran Raz

doi:10.1109/FOCS.2014.27

Exponential separation of information and communication

Anat Ganor, Gillat Kol, Ran Raz

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

37 Scopus citations

Abstract

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

Original language	English (US)
Title of host publication	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Publisher	IEEE Computer Society
Pages	176-185
Number of pages	10
ISBN (Electronic)	9781479965175
DOIs	https://doi.org/10.1109/FOCS.2014.27
State	Published - Dec 7 2014
Externally published	Yes
Event	55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 - Philadelphia, United States Duration: Oct 18 2014 → Oct 21 2014

Publication series

Name	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)	0272-5428

Other

Other	55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014
Country/Territory	United States
City	Philadelphia
Period	10/18/14 → 10/21/14

All Science Journal Classification (ASJC) codes

General Computer Science

Keywords

Information complexity
amortized communication complexity
communication complexity
communication compression
direct sum

Access to Document

10.1109/FOCS.2014.27

Cite this

@inproceedings{43c87a23d0964cdda02406639bb2201e,

title = "Exponential separation of information and communication",

abstract = "We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.",

keywords = "Information complexity, amortized communication complexity, communication complexity, communication compression, direct sum",

author = "Anat Ganor and Gillat Kol and Ran Raz",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 ; Conference date: 18-10-2014 Through 21-10-2014",

year = "2014",

month = dec,

day = "7",

doi = "10.1109/FOCS.2014.27",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "176--185",

booktitle = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

address = "United States",

}

Ganor, A, Kol, G & Raz, R 2014, Exponential separation of information and communication. in Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS., 6979002, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, IEEE Computer Society, pp. 176-185, 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, United States, 10/18/14. https://doi.org/10.1109/FOCS.2014.27

Exponential separation of information and communication. / Ganor, Anat; Kol, Gillat ; Raz, Ran.
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. IEEE Computer Society, 2014. p. 176-185 6979002 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

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

TY - GEN

T1 - Exponential separation of information and communication

AU - Ganor, Anat

AU - Kol, Gillat

AU - Raz, Ran

PY - 2014/12/7

Y1 - 2014/12/7

N2 - We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

AB - We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity ≤ O(k), and distributional communication complexity ≥ 2k. This shows that a communication protocol cannot always be compressed to its internal information. By a result of Braverman [1], our gap is the largest possible. By a result of Braverman and Rao [2], our example shows a gap between communication complexity and amortized communication complexity, implying that a tight direct sum result for distributional communication complexity cannot hold.

KW - Information complexity

KW - amortized communication complexity

KW - communication complexity

KW - communication compression

KW - direct sum

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

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

U2 - 10.1109/FOCS.2014.27

DO - 10.1109/FOCS.2014.27

M3 - Conference contribution

AN - SCOPUS:84920049144

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 176

EP - 185

BT - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

PB - IEEE Computer Society

T2 - 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014

Y2 - 18 October 2014 through 21 October 2014

ER -

Exponential separation of information and communication

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this