Information complexity and applications.

DOI10.1007/s11537-018-1727-9zbMath1417.68040MaRDI QIDQ1731897

Mark Braverman

Publication date: 14 March 2019

Published in: Japanese Journal of Mathematics. 3rd Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11537-018-1727-9

zbMATH Keywords

survey paper; information complexity; communication complexity

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

94A15: Information theory (general)

94A24: Coding theorems (Shannon theory)

94A29: Source coding