Information complexity and applications.

DOI10.1007/S11537-018-1727-9MaRDI QIDQ1731897zbMATH OpenOpenAlexFDO

Authors 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

communication complexityinformation complexitysurvey paper

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24) Source coding (94A29)

Recommendations

• Interactive information complexity
• Information complexity is computable
• Interactive Information Complexity
• Interactive information complexity
• On information complexity in the broadcast model

Cites work

• A Parallel Repetition Theorem
• Amortized Communication Complexity
• An information statistics approach to data stream and communication complexity
• An interactive information odometer and applications
• An introduction to Kolmogorov complexity and its applications
• Communication Complexity
• Communication lower bounds using directional derivatives
• Computing with Noisy Information
• Exponential separation of communication and external information
• Exponential Separation of Information and Communication for Boolean Functions
• From information to exact communication
• How to compress interactive communication
• scientific article; zbMATH DE number 1306882 (Why is no real title available?)
• Information complexity is computable
• Information Equals Amortized Communication
• Interactive compression for product distributions
• Interactive information and coding theory
• Interactive Information Complexity
• Lower bounds in communication complexity
• On the distributional complexity of disjointness
• Parallel repetition in projection games and a concentration bound
• Private vs. common random bits in communication complexity
• Public vs private coin in bounded-round information
• Small value parallel repetition for general games
• Some Results on Distributed Source Coding for Interactive Function Computation
• Super-logarithmic depth lower bounds via the direct sum in communication complexity
• The Infinite-Message Limit of Two-Terminal Interactive Source Coding
• The Probabilistic Communication Complexity of Set Intersection

Cited in

(2)

• An introductory course on communication complexity
• scientific article; zbMATH DE number 53549 (Why is no real title available?)

This page was built for publication: Information complexity and applications.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1731897)