Interactive Information Complexity
From MaRDI portal
Publication:4592949
DOI10.1137/17M1139254zbMath1380.68177OpenAlexW2767315450MaRDI QIDQ4592949
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
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) Measures of information, entropy (94A17) Source coding (94A29)
Related Items
The Communication Complexity of Set Intersection and Multiple Equality Testing, Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Mathematical Theory of Communication
- A direct product theorem for two-party bounded-round public-coin communication complexity
- A discrepancy lower bound for information complexity
- An information statistics approach to data stream and communication complexity
- Disjointness is hard in the multiparty number-on-the-forehead model
- Lower bounds on the randomized communication complexity of read-once functions
- On the power of small-depth threshold circuits
- Quantum and approximate privacy
- A characterization of average case communication complexity
- On the distributional complexity of disjointness
- Lower bounds for one-way probabilistic communication complexity and their application to space complexity
- Towards proving strong direct product theorems
- Individual communication complexity
- How to Compress Interactive Communication
- A strong direct product theorem for disjointness
- Quantum Information Complexity
- Small Value Parallel Repetition for General Games
- An Interactive Information Odometer and Applications
- Pseudorandom Generators for Regular Branching Programs
- Parallel Repetition in Projection Games and a Concentration Bound
- Relative Discrepancy Does not Separate Information and Communication Complexity
- Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
- A property of quantum relative entropy with an application to privacy in quantum communication
- Interactive Information Complexity
- Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas
- Worst-case interactive communication. II. Two messages are not optimal
- Worst-case interactive communication. I. Two messages are almost optimal
- The Probabilistic Communication Complexity of Set Intersection
- Privacy, additional information and communication
- A Parallel Repetition Theorem
- Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness
- Information complexity is computable
- Amortized Communication Complexity
- Communication Complexity
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
- Information Lower Bounds via Self-reducibility
- The Communication Complexity of Correlation
- Interaction in quantum communication and the complexity of set disjointness
- Some Results on Distributed Source Coding for Interactive Function Computation
- Direct Product via Round-Preserving Compression
- Exponential separation of communication and external information
- The multiparty communication complexity of set disjointness
- Quantum one-way communication can be exponentially stronger than classical communication
- Information Equals Amortized Communication
- From information to exact communication
- Communication Lower Bounds Using Directional Derivatives
- 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
