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

survey papercommunication complexityinformation complexity

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1306882 (Why is no real title available?)
• 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 Information and Communication for Boolean Functions
• Exponential separation of communication and external information
• From information to exact communication
• How to compress interactive communication
• Information Equals Amortized Communication
• Information complexity is computable
• Interactive Information Complexity
• Interactive compression for product distributions
• Interactive information and coding theory
• 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)