Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications

DOI10.1137/130928273zbMath1330.68096arXiv1204.1505OpenAlexW2571088576MaRDI QIDQ3449568

Virginie Lerays, Iordanis Kerenidis, Jérémie Roland, Sophie Laplante, David Xiao

Publication date: 4 November 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.1505

zbMATH Keywords

information complexitycommunication complexityzero-communication protocols

Mathematics Subject Classification ID

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)

Related Items

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Interactive Information Complexity ⋮ Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ A discrepancy lower bound for information complexity ⋮ Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness ⋮ Unnamed Item ⋮ Approximate nonnegative rank is equivalent to the smooth rectangle bound ⋮ Information value of two-prover games ⋮ Quantum conditional mutual information and approximate Markov chains ⋮ Information lower bounds via self-reducibility ⋮ Unnamed Item ⋮ Simulation theorems via pseudo-random properties ⋮ Rectangles Are Nonnegative Juntas ⋮ Lifting Theorems for Equality ⋮ Unnamed Item ⋮ Exponential Separation of Communication and External Information ⋮ Communication Complexity of Statistical Distance ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets ⋮ 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 discrepancy lower bound for information complexity
• An information statistics approach to data stream and communication complexity
• Quantum and approximate privacy
• A local hidden variable model of quantum correlation exploiting the detection loophole
• Classical and Quantum Partition Bound and Detector Inefficiency
• How to Compress Interactive Communication
• The Hardness of Being Private
• The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited
• Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming
• Lower Bounds in Communication Complexity
• Two applications of information complexity
• Privacy, additional information and communication
• An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance
• Information Lower Bounds via Self-reducibility
• Approximate Privacy
• The Communication Complexity of Correlation
• En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations
• Interactive information complexity
• Tight bounds for distributed functional monitoring
• Quantum one-way communication can be exponentially stronger than classical communication
• Information Equals Amortized Communication
• Lower bounds in communication complexity based on factorization norms

This page was built for publication: Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications