# Questions tagged [communication-complexity]

Questions regarding the amount of communication needed to accomplish a computational task, when the information about the task is spread across several agents

143 questions
Filter by
Sorted by
Tagged with
66 views

### On $PP$ vs $\oplus P$ in CC

In communication complexity is it known that the classes $PP^{cc}$ and $\oplus P^{cc}$ satisfy $PP^{cc}\not\subseteq\oplus P^{cc}$?
• 13k
1 vote
23 views

### How to calculate the data transmission rate with path-loss?

We aim to calculate the data transmission rate when sending results from the server back to the user's device. Using the notation: ( B_v ): wireless bandwidth of the server ( P_v ): server's ...
120 views

### Why is showing lower bounds for AM communication complexity difficult?

One of the major open problems in communication complexity is to show interesting lower bounds for the Arthur-Merlin (AM) communication complexity of some natural problems (i.e., lower bounds of the ...
• 686
32 views

• 49
1 vote
77 views

### communication complexity lower bound for identifying coordinate in which two strings differ

This is a question from Rao and Yehudayoff's "Communication Complexity and Applications" textbook that I've been thinking about for a while. Suppose Alice has a string $x\in\{0,1\}^n$ that ...
• 49
69 views

### Communication complexity of correctly recovering 99% of a random bit string

Suppose Alice has a bit string of length $n$ where $n/2$ bits are chosen uniformly at random to be 1's; and the rest are 0's. Alice sends a message to Bob. If Bob needs to reconstruct the bit string, ...
161 views

• 11
151 views

### Nondeterministic communication complexity

Let $X$ and $Y$ be finite sets and $f : X \times Y \to \{0,1\}$. I am confused about the definition of the deterministic communication complexity of $f$, denoted $N^1(f)$, or rather about the ...
• 251
213 views

• 1,049
1 vote
74 views

### Algorithmic game theory with decentralized mechanism of exchanging information

An interesting topic that I want to understand has to do with the decentralized exchange of information among a network of agents, however there is not a specific theory to make such a mathematical ...
• 209
1 vote
118 views

### Communication complexity of reconstructing a random bit-string of length $n$

This seems like a folklore claim but I cannot find any reference to it. If Alice has a bit-string of length $n$ where each entry is independently set to 0 or 1 equiprobably, and Bob's goal is to ...
1 vote
128 views

### Deterministic one way communication complexity for message with arbitrary length

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message. I have been looking into ...
172 views

### Multi-round communication complexity of greater than

For the "greater-than" problem in Yao's 2-party communication complexity model, Alice receives $X$ and Bob receives $Y$, and they need to decide whether $X>Y$. I recently listened to an (...
179 views

• 113
99 views

• 11
102 views

### Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
• 213
1 vote
426 views

### Minimum number of hours of speech needed to train a neural net to recognize speech [closed]

From a theoretical computer science point of view, is there a lower limit on the number of hours of speech needed to train a neural net to translate speech to text? An estimate from CMU is 3000-5000 ...
• 107
1 vote
77 views

### Bipartite formula complexity lower bound

I'm trying to understand the paper The Bipartite Formula Complexity of Inner Product is Quadratic, by Avishay Tal. The argument is recapped here. I am having trouble understanding the proof Theorem 3 ...
• 123
132 views

### What is the communication complexity of approximating addition?

In my circuit complexity research, I came across the need to find the communication complexity of approximating addition. Specifically, the class of problems I am interested in is parametrized by four ...
• 653
1 vote
97 views

• 223
139 views

256 views

• 123
79 views

### Relationship between worst case length of transcript and entropy of transcript

Consider the two party model of communication complexity where Alice and Bob are given inputs $X$ and $Y$ sampled from some distribution $\mu$, and their goal is to solve some problem $P$ (the details ...
• 11
188 views

### 0-partition number vs partition number

Denote by $\chi_0(f)$ the minimum number of 0 monochromatic rectangles needed to cover the 0-inputs of $f$, and by $\chi(f)$ the minimum number of monochromatic rectangles needed to cover the all ...
• 345
1 vote
51 views

### What is the best known gap between ZPP and Deterministic communication complexity? [duplicate]

I know that $N(f) \times coN(f) \geq D(f)$. This means that $ZPP(f) \geq \sqrt{D(f)}$. Is this separation tight?
• 901
1 vote