Information complexity and applications.
From MaRDI portal
Publication:1731897
DOI10.1007/s11537-018-1727-9zbMath1417.68040OpenAlexW2915610068MaRDI QIDQ1731897
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
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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24) Source coding (94A29)
Cites Work
- Unnamed Item
- Unnamed Item
- A discrepancy lower bound for information complexity
- An information statistics approach to data stream and communication complexity
- Private vs. common random bits in communication complexity
- On the distributional complexity of disjointness
- Super-logarithmic depth lower bounds via the direct sum in communication complexity
- How to Compress Interactive Communication
- Small Value Parallel Repetition for General Games
- An Interactive Information Odometer and Applications
- Parallel Repetition in Projection Games and a Concentration Bound
- Lower Bounds in Communication Complexity
- Interactive Information Complexity
- The Probabilistic Communication Complexity of Set Intersection
- Computing with Noisy Information
- A Parallel Repetition Theorem
- Information complexity is computable
- Amortized Communication Complexity
- Communication Complexity
- Public vs Private Coin in Bounded-Round Information
- Some Results on Distributed Source Coding for Interactive Function Computation
- The Infinite-Message Limit of Two-Terminal Interactive Source Coding
- Exponential separation of communication and external information
- Interactive compression for product distributions
- Information Equals Amortized Communication
- From information to exact communication
- Communication lower bounds using directional derivatives
- Exponential Separation of Information and Communication for Boolean Functions
- An introduction to Kolmogorov complexity and its applications
