Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2304.00391 · Lecture notes in computer science

The Communication Complexity of Functions with Large Outputs

Lila Fontes, Sophie Laplante, Mathieu Laurière, Alexandre Nolin

Published Jan 1, 2023• 0 citations
arXivHTMLPDF
DOI
10.1007/978-3-031-32733-9_19

Related papers

Note on Complexity of Communication Processes

Noboru Watanabe

Springer proceedings in mathematics & statistics•Jan 1, 2022•0 citations

On the Communication Complexity of Secure Function Evaluation with Long Output

Pavel Hubáček, Daniel Wichs

We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input χA, Bob has an input χB and we want Bob to learn some function y = f(χA, χB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input χA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such 'output-size dependence' inherent in SFE'

Conference on Innovations in Theoretical Computer Science•Jan 11, 2015•132 citations

Bell Nonlocality Universally Confirmed In Any Large Communication Complexity Advantage, Bell Nonlocal Correlations, Communication Complexity And The Violation Of A Bell Inequality, Communication Complexity And The Violation Of A Bell Inequality-2, Exchang

K.N.P. Kumar

We study the following system with concomitant properties: Bell Nonlocality Universally Confirmed In Any Large Communication Complexity Advantage, Bell Nonlocal Correlations, Communication Complexity And The Violation Of A Bell Inequality, Communication Complexity And The Violation Of A Bell Inequality-2, Exchange Of The Information After Simultaneous Teleportation To Reveal The Path Of The Teleported System In A Three-Round Protocol, Efficient Teleportation Protocol, Protocols That Use Initial Entanglement Should Be Even More Explicitly Bell Nonlocal, Classical And Quantum Communication Complexity, Asymptotic Teleportation Scheme : Universal Programmable Quantum Processor, Quantum Teleportation Scheme By Selecting One Of Multiple Output Ports, String Theory Basics The full paper: http://www.iiste.org/PDFshare/APTA-PAGENO-586138-592334.pdf

Advances in physics theories and applications•Jan 1, 2013•0 citations

The Communication Complexity of Non-signaling Distributions

Julien Degorre, Marc Kaplan, Sophie Laplante +1 more

arXiv:0804.4859•Lecture notes in computer science•Jan 1, 2009•53 citations

On the power of quantum proofs

Ran Raz, Amir Shpilka

We study the power of quantum proofs, or more precisely, the power of Quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the Linear Subspaces Distance problem. The problem is of geometrical nature: Each player gets a linear subspace of R m and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 · √ 2) and 0 if the distance is very large (say, larger than 0.9 · √ 2). We show that: 1. The QMA communication complexity of the problem is O(log m). 2. The (classical) MA communication complexity of the problem is Ω(m ɛ) (for some ɛ> 0). 3. The (standard) quantum communication complexity of the problem is Ω ( √ m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity.

Conference on Computational Complexity•Jun 21, 2004•31 citations

Dimension-free bounds and structural results in communication complexity

Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

Israel Journal of Mathematics•Oct 20, 2022•22 citations
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input χA, Bob has an input χB and we want Bob to learn some function y = f(χA, χB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input χA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such 'output-size dependence' inherent in SFE'
We study the following system with concomitant properties: Bell Nonlocality Universally Confirmed In Any Large Communication Complexity Advantage, Bell Nonlocal Correlations, Communication Complexity And The Violation Of A Bell Inequality, Communication Complexity And The Violation Of A Bell Inequality-2, Exchange Of The Information After Simultaneous Teleportation To Reveal The Path Of The Teleported System In A Three-Round Protocol, Efficient Teleportation Protocol, Protocols That Use Initial Entanglement Should Be Even More Explicitly Bell Nonlocal, Classical And Quantum Communication Complexity, Asymptotic Teleportation Scheme : Universal Programmable Quantum Processor, Quantum Teleportation Scheme By Selecting One Of Multiple Output Ports, String Theory Basics The full paper: http://www.iiste.org/PDFshare/APTA-PAGENO-586138-592334.pdf
We study the power of quantum proofs, or more precisely, the power of Quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the Linear Subspaces Distance problem. The problem is of geometrical nature: Each player gets a linear subspace of R m and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 · √ 2) and 0 if the distance is very large (say, larger than 0.9 · √ 2). We show that: 1. The QMA communication complexity of the problem is O(log m). 2. The (classical) MA communication complexity of the problem is Ω(m ɛ) (for some ɛ> 0). 3. The (standard) quantum communication complexity of the problem is Ω ( √ m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity.