Questions tagged [communication-complexity]

Communication complexity studies the amount of communication required to solve a problem when the input to the problem is distributed among two or more parties. It was introduced by Andrew Yao in 1979. (Wikipedia)

Filter by
Sorted by
Tagged with
8 votes
2 answers

Resources for Quantum Communication Complexity

I recently came to know about this interesting topic of "communication complexity". In simple words, Wikipedia defines it as: In theoretical computer science, communication complexity studies the ...
Sanchayan Dutta's user avatar
6 votes
1 answer

Could quantum computers be useful for sending encrypted information over a classical channel?

A quantum computer running Shor's algorithm would be famously useful for decrypting information encrypted by many classical public-key cryptography algorithms. Is there any reason (either a specific ...
tparker's user avatar
  • 2,551
3 votes
1 answer

Complexity of quantum circuits in a specific protocol

Consider the following simultaneous communication problem. Alice and Bob do not share any entanglement or any common randomness, and cannot communicate directly with each other. As inputs, $x$ is ...
Shlomo's user avatar
  • 31