Interactive Information Complexity
From MaRDI portal
Publication:3454520
DOI10.1137/130938517zbMath1330.68067OpenAlexW2201563107MaRDI QIDQ3454520
Publication date: 25 November 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/130938517
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (17)
Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ Direct sum fails for zero-error average communication ⋮ Some lower bounds in dynamic networks with oblivious adversaries ⋮ Communication complexity with small advantage ⋮ The communication complexity of functions with large outputs ⋮ The work of Mark Braverman ⋮ Communication and information complexity ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Information complexity and applications. ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Exponential Separation of Communication and External Information ⋮ Communication Complexity of Statistical Distance ⋮ Trading information complexity for error. II: The case of a large error and the external information complexity
Cites Work
- 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
- Information Equals Amortized Communication
- Pseudorandom Generators for Regular Branching Programs
- 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
- 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
- Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness
- 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
- 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
This page was built for publication: Interactive Information Complexity
