Near-Optimal Bounds on the Bounded-Round Quantum Communication Complexity of Disjointness
From MaRDI portal
Publication:4562275
DOI10.1137/16M1061400zbMath1408.68062arXiv1505.03110OpenAlexW2905051967WikidataQ128722761 ScholiaQ128722761MaRDI QIDQ4562275
Ankit Garg, Jieming Mao, Young Kun-Ko, Mark Braverman, Dave Touchette
Publication date: 19 December 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1505.03110
Related Items
Interactive Information Complexity, Interactive Information Complexity, Bounds on oblivious multiparty quantum communication complexity, Unnamed Item, The work of Mark Braverman, Communication and information complexity, The complexity of quantum disjointness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Common information and unique disjointness
- Quantum conditional mutual information and approximate Markov chains
- An information statistics approach to data stream and communication complexity
- On the distributional complexity of disjointness
- Exponential separation of quantum and classical communication complexity
- How to compress interactive communication
- Quantum Information Complexity
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Certifying Equality With Limited Interaction.
- The Fidelity of Recovery Is Multiplicative
- Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications
- Exponential Separation of Quantum and Classical One-Way Communication Complexity
- Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
- The Probabilistic Communication Complexity of Set Intersection
- Rounds in Communication Complexity Revisited
- Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
- Communication Complexity
- Strong Direct Product Theorems for Quantum Communication and Query Complexity
- Information Lower Bounds via Self-reducibility
- Interaction in quantum communication and the complexity of set disjointness
- Direct Product via Round-Preserving Compression
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States
- Entangled simultaneity versus classical interactivity in communication complexity
- Exponential separation of communication and external information
- Interactive information complexity
- Quantum one-way communication can be exponentially stronger than classical communication
- Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
- From information to exact communication
- An information complexity approach to extended formulations
- Communication Lower Bounds Using Directional Derivatives
- Some Minimax Theorems.
- Quantum Information Theory
- Concentration of Measure for the Analysis of Randomized Algorithms
- The communication complexity of pointer chasing
