# 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

142 questions
Filter by
Sorted by
Tagged with
1 vote
16 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 ...
104 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 ...
31 views

1 vote
71 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 ...
68 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, ...
158 views

136 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 ...
211 views

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 ...
1 vote
117 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
125 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 ...
148 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 (...
1 vote
164 views

98 views

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 ...
1 vote
366 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 ...
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 ...
129 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 ...
1 vote
92 views

139 views

249 views

77 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 ...
186 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 ...
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?
1 vote