Information complexity and applications: Takagi Lectures Notes

Mark Braverman

doi:10.1007/s11537-018-1727-9

Information complexity and applications: Takagi Lectures Notes

Mark Braverman

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

This paper is a lecture note accompanying the 19th Takagi Lectures lectures in July 2017 at Kyoto University. We give a high-level overview of information complexity theory and its connections to communication complexity.We then discuss some fundamental properties of information complexity, and applications to direct sum theorems and to exact communication bounds. We conclude with some open questions and directions.

Original language	English (US)
Pages (from-to)	27-65
Number of pages	39
Journal	Japanese Journal of Mathematics
Volume	14
Issue number	1
DOIs	https://doi.org/10.1007/s11537-018-1727-9
State	Published - Mar 1 2019
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

communication complexity
information complexity

Access to Document

10.1007/s11537-018-1727-9

Cite this

@article{cc9d8920f416433ba72bdff81e69ffc2,

title = "Information complexity and applications: Takagi Lectures Notes",

abstract = "This paper is a lecture note accompanying the 19th Takagi Lectures lectures in July 2017 at Kyoto University. We give a high-level overview of information complexity theory and its connections to communication complexity.We then discuss some fundamental properties of information complexity, and applications to direct sum theorems and to exact communication bounds. We conclude with some open questions and directions.",

keywords = "communication complexity, information complexity",

author = "Mark Braverman",

note = "Publisher Copyright: {\textcopyright} 2019, The Mathematical Society of Japan and Springer Japan KK, part of Springer Nature.",

year = "2019",

month = mar,

day = "1",

doi = "10.1007/s11537-018-1727-9",

language = "English (US)",

volume = "14",

pages = "27--65",

journal = "Japanese Journal of Mathematics",

issn = "0289-2316",

publisher = "Springer Japan",

number = "1",

}

TY - JOUR

T1 - Information complexity and applications

T2 - Takagi Lectures Notes

AU - Braverman, Mark

PY - 2019/3/1

Y1 - 2019/3/1

N2 - This paper is a lecture note accompanying the 19th Takagi Lectures lectures in July 2017 at Kyoto University. We give a high-level overview of information complexity theory and its connections to communication complexity.We then discuss some fundamental properties of information complexity, and applications to direct sum theorems and to exact communication bounds. We conclude with some open questions and directions.

AB - This paper is a lecture note accompanying the 19th Takagi Lectures lectures in July 2017 at Kyoto University. We give a high-level overview of information complexity theory and its connections to communication complexity.We then discuss some fundamental properties of information complexity, and applications to direct sum theorems and to exact communication bounds. We conclude with some open questions and directions.

KW - communication complexity

KW - information complexity

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

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

U2 - 10.1007/s11537-018-1727-9

DO - 10.1007/s11537-018-1727-9

M3 - Article

AN - SCOPUS:85062595989

SN - 0289-2316

VL - 14

SP - 27

EP - 65

JO - Japanese Journal of Mathematics

JF - Japanese Journal of Mathematics

IS - 1

ER -

Information complexity and applications: Takagi Lectures Notes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this