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

Lecture notes in computer science

Relations Between Communication Complexity, Linear Arrangements, and Computational Complexity

Jürgen Forster, Matthias Krause, Satyanarayana V. Lokam, Rustam Mubarakzjanov, Niels Schmitt, Hans Ulrich Simon

Published Jan 1, 2001• 87 citations
Publisher
DOI
10.1007/3-540-45294-x_15

Related papers

Robust Multiparty Computation with Linear Communication Complexity

Martin Hirt, Jesper Buus Nielsen

Lecture notes in computer science•Jan 1, 2006•66 citations

Asynchronous Multiparty Computation with Linear Communication Complexity

Ashish Choudhury, Martin Hirt, Arpita Patra

Lecture notes in computer science•Jan 1, 2013•34 citations

Asynchronous Multiparty Computation with Linear Communication Complexity

Choudhary, Ashish, Martin Hirt, Arpita Patra

•Jan 1, 2013•0 citations

Unbounded-error classical and quantum communication complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond +1 more

Abstract. Since the seminal work of Paturi and Simon [25, FOCS’84 & JCSS’86], the unboundederror classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [13, ICALP’07] found that the unbounded-error quantum communication complexity in the one-way communication model can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to the two-way and simultaneous message passing (SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is used to show that the gap between weakly unbounded-error quantum and classical communication complexities is at most a factor of three. 1

•Jan 1, 2007•4 citations

Composition Theorems in Communication Complexity

Troy Lee, Shengyu Zhang

arXiv:1003.1443•Lecture notes in computer science•Jan 1, 2010•33 citations

On the Hardness of Information-Theoretic Multiparty Computation

Yuval Ishai, Eyal Kushilevitz Z

Abstract We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity of the function being computed? For instance, can computationally unbounded players compute an arbitrary function of their inputs with polynomial communication complexity and a linear threshold of unconditional privacy? Can this be done using a constant number of communication rounds? We provide an explanation for the difficulty of resolving these questions by showing that they are closely related to the problem of obtaining efficient protocols for (information-theoretic) private information retrieval and hence also to the problem of constructing short locally-decodable error-correcting codes. The latter is currently considered to be among the most intriguing open problems in complexity theory. Keywords. Information-theoretic cryptography, secure multiparty computation, private information retrieval, locally decodable codes. 1 Introduction In STOC 1990, Beaver, Micali, and Rogaway [5] posed the following question: Is there a constant-round protocol that allows k computationally unbounded players to defeat a computationally unbounded adversary, while using only a polynomial amount of communication in the total length of their inputs?

•Jan 1, 2004•0 citations
Abstract. Since the seminal work of Paturi and Simon [25, FOCS’84 & JCSS’86], the unboundederror classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [13, ICALP’07] found that the unbounded-error quantum communication complexity in the one-way communication model can also be investigated using the arrangement, and showed that it is exactly (without a difference of even one qubit) half of the classical one-way communication complexity. In this paper, we extend the arrangement argument to the two-way and simultaneous message passing (SMP) models. As a result, we show similarly tight bounds of the unbounded-error two-way/one-way/SMP quantum/classical communication complexities, implying that all of them are equivalent up to a multiplicative constant of four. Moreover, the arrangement argument is used to show that the gap between weakly unbounded-error quantum and classical communication complexities is at most a factor of three. 1
Abstract We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity of the function being computed? For instance, can computationally unbounded players compute an arbitrary function of their inputs with polynomial communication complexity and a linear threshold of unconditional privacy? Can this be done using a constant number of communication rounds? We provide an explanation for the difficulty of resolving these questions by showing that they are closely related to the problem of obtaining efficient protocols for (information-theoretic) private information retrieval and hence also to the problem of constructing short locally-decodable error-correcting codes. The latter is currently considered to be among the most intriguing open problems in complexity theory. Keywords. Information-theoretic cryptography, secure multiparty computation, private information retrieval, locally decodable codes. 1 Introduction In STOC 1990, Beaver, Micali, and Rogaway [5] posed the following question: Is there a constant-round protocol that allows k computationally unbounded players to defeat a computationally unbounded adversary, while using only a polynomial amount of communication in the total length of their inputs?