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

Related Items (20)

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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