Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
From MaRDI portal
Publication:3449568
DOI10.1137/130928273zbMath1330.68096arXiv1204.1505MaRDI 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
68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, Interactive Information Complexity, Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness, Rectangles Are Nonnegative Juntas, Superlinear lower bounds for multipass graph processing, A discrepancy lower bound for information complexity, Quantum conditional mutual information and approximate Markov chains, Information lower bounds via self-reducibility, Simulation theorems via pseudo-random properties, Approximate nonnegative rank is equivalent to the smooth rectangle bound, Relative Discrepancy Does not Separate Information and Communication Complexity, Interactive 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
