Bare quantum simultaneity versus classical interactivity in communication complexity
Dmitry Gavinsky
2020年份
14被引次数
2顶会引用
摘要
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了最后一个公式，引用它的顶会 Paper 也一样。你提问，回答直接引用原文。
引用它的顶会 Paper2
- Magic and Communication ComplexityUma Girish, Alex May, Natalie Parham, Henry YuenSTOC 2026 · 被引用 5 次
- Quantum Communication Advantage in TFNPMika Göös, Tom Gur, Siddhartha Jain, Jiawei LiSTOC 2025
相关 Paper
- The impossibility of efficient quantum weak coin flippingCarl A. MillerSTOC 2020 · 被引用 9 次
- Binary Codes with Resilience Beyond 1/4 via InteractionKlim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun ZhangFOCS 2022 · 被引用 3 次
- 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 次
- On the Round Complexity of Secure Quantum ComputationJames Bartusek, Andrea Coladangelo, Dakshita Khurana, Fermi MaCRYPTO 2021 · 被引用 24 次
