Information complexity density and simulation of protocols

Himanshu Tyagi, Shaileshh Bojja Venkatakrishnan, Pramod Viswanath, Shun Watanabe

Research output: Contribution to journalArticle

Abstract

Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

Original languageEnglish (US)
Article number8022868
Pages (from-to)6979-7002
Number of pages24
JournalIEEE Transactions on Information Theory
Volume63
Issue number11
DOIs
StatePublished - Nov 2017

Fingerprint

Network protocols
simulation
communication
Communication
Random variables
computer science
Computer science

Keywords

  • Compression of protocols
  • Information complexity
  • Interactive communication
  • Secret key agreement

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

Information complexity density and simulation of protocols. / Tyagi, Himanshu; Venkatakrishnan, Shaileshh Bojja; Viswanath, Pramod; Watanabe, Shun.

In: IEEE Transactions on Information Theory, Vol. 63, No. 11, 8022868, 11.2017, p. 6979-7002.

Research output: Contribution to journalArticle

Tyagi, Himanshu ; Venkatakrishnan, Shaileshh Bojja ; Viswanath, Pramod ; Watanabe, Shun. / Information complexity density and simulation of protocols. In: IEEE Transactions on Information Theory. 2017 ; Vol. 63, No. 11. pp. 6979-7002.
@article{f0715f27d4234b9497468aa8f4727688,
title = "Information complexity density and simulation of protocols",
abstract = "Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.",
keywords = "Compression of protocols, Information complexity, Interactive communication, Secret key agreement",
author = "Himanshu Tyagi and Venkatakrishnan, {Shaileshh Bojja} and Pramod Viswanath and Shun Watanabe",
year = "2017",
month = "11",
doi = "10.1109/TIT.2017.2746859",
language = "English (US)",
volume = "63",
pages = "6979--7002",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "11",

}

TY - JOUR

T1 - Information complexity density and simulation of protocols

AU - Tyagi, Himanshu

AU - Venkatakrishnan, Shaileshh Bojja

AU - Viswanath, Pramod

AU - Watanabe, Shun

PY - 2017/11

Y1 - 2017/11

N2 - Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

AB - Two parties observing correlated random variables seek to run an interactive communication protocol. How many bits must they exchange to simulate the protocol, namely to produce a view with a joint distribution within a fixed statistical distance of the joint distribution of the input and the transcript of the original protocol? We present an information spectrum approach for this problem whereby the information complexity of the protocol is replaced by its information complexity density. Our single-shot bounds relate the communication complexity of simulating a protocol to tail bounds for information complexity density. As a consequence, we obtain a strong converse and characterize the second-order asymptotic term in communication complexity for independent and identically distributed observation sequences. Furthermore, we obtain a general formula for the rate of communication complexity, which applies to any sequence of observations and protocols. Connections with results from theoretical computer science and implications for the function computation problem are discussed.

KW - Compression of protocols

KW - Information complexity

KW - Interactive communication

KW - Secret key agreement

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

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

U2 - 10.1109/TIT.2017.2746859

DO - 10.1109/TIT.2017.2746859

M3 - Article

AN - SCOPUS:85028714841

VL - 63

SP - 6979

EP - 7002

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 11

M1 - 8022868

ER -