Interactive information complexity
From MaRDI portal
Publication:4592949
DOI10.1137/17M1139254zbMATH Open1380.68177OpenAlexW2767315450MaRDI QIDQ4592949FDOQ4592949
Authors: Mark Braverman 
Publication date: 9 November 2017
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1139254
Recommendations
Measures of information, entropy (94A17) 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)
Cites Work
- Title not available (Why is that?)
- A Mathematical Theory of Communication
- Worst-case interactive communication. I. Two messages are almost optimal
- The Probabilistic Communication Complexity of Set Intersection
- Communication Complexity
- On the power of small-depth threshold circuits
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- The multiparty communication complexity of set disjointness
- An information statistics approach to data stream and communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- A Parallel Repetition Theorem
- On the distributional complexity of disjointness
- Towards proving strong direct product theorems
- How to compress interactive communication
- A strong direct product theorem for disjointness
- An interactive information odometer and applications
- A direct product theorem for two-party bounded-round public-coin communication complexity
- Relative discrepancy does not separate information and communication complexity
- Lower bounds on information complexity via zero-communication protocols and applications
- Interactive Information Complexity
- Privacy, additional information and communication
- Title not available (Why is that?)
- Amortized Communication Complexity
- Information Lower Bounds via Self-reducibility
- The Communication Complexity of Correlation
- Interaction in quantum communication and the complexity of \textsc{Set Disjointness}
- Direct product via round-preserving compression
- Information Equals Amortized Communication
- From information to exact communication
- Noiseless coding of correlated information sources
- Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
- Exponential Separation of Information and Communication for Boolean Functions
- Quantum and approximate privacy
- Parallel repetition in projection games and a concentration bound
- A property of quantum relative entropy with an application to privacy in quantum communication
- Some Results on Distributed Source Coding for Interactive Function Computation
- Individual communication complexity
- Lower bounds on the randomized communication complexity of read-once functions
- Quantum information complexity
- A characterization of average case communication complexity
- Simplified lower bounds on the multiparty communication complexity of disjointness
- Worst-case interactive communication. II. Two messages are not optimal
- Quantum one-way communication can be exponentially stronger than classical communication
- Small value parallel repetition for general games
- Information complexity is computable
- Exponential separation of communication and external information
- Communication lower bounds using directional derivatives
- The communication complexity of gap Hamming distance
- Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
- Pseudorandom generators for regular branching programs
- Near-optimal bounds on the bounded-round quantum communication complexity of disjointness
- Title not available (Why is that?)
Cited In (9)
- Trading information complexity for error
- Information complexity and applications.
- Interactive Information Complexity
- On information complexity in the broadcast model
- Query-to-communication lifting using low-discrepancy gadgets
- Information complexity is computable
- Interactive information complexity
- From information to exact communication
- The communication complexity of set intersection and multiple equality testing
This page was built for publication: Interactive information complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592949)
