Bare quantum simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky
2020Year
14Citations
2Top-tier citations
Abstract
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 1fdd5f67-6b59-43cc-a643-566f35d8ea7aCited by top-tier papers2
- Magic and Communication ComplexityUma Girish, Alex May, Natalie Parham, Henry YuenSTOC 2026 · 5 citations
- Quantum Communication Advantage in TFNPMika Göös, Tom Gur, Siddhartha Jain, Jiawei LiSTOC 2025
Related papers
- The impossibility of efficient quantum weak coin flippingCarl A. MillerSTOC 2020 · 9 citations
- Binary Codes with Resilience Beyond 1/4 via InteractionKlim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun ZhangFOCS 2022 · 3 citations
- Classical Simulation of Quantum CSP StrategiesDemian Banakh, Lorenzo Ciardo, Marcin Kozik, Jan TulowieckiLICS 2025
- Black-Box Separations for Non-interactive Classical Commitments in a Quantum WorldKai-Min Chung, Yao-Ting Lin, Mohammad MahmoodyEUROCRYPT 2023 · 7 citations
- On the Round Complexity of Secure Quantum ComputationJames Bartusek, Andrea Coladangelo, Dakshita Khurana, Fermi MaCRYPTO 2021 · 24 citations
