# 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
2 votes
1 answer
135 views

### Partition Number of a Matrix

Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known ...
• 12.9k
2 votes
1 answer
181 views

### Why not include private randomness in internal communication information definition?

I am using https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf as a reference. This isn't exactly a research question but I can't find a good place to ask it. Suppose ...
• 123
2 votes
1 answer
323 views

### "Send Once"-One way Multiparty Communication Complexity

There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting. I want to consider more ...
2 votes
1 answer
146 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
2 votes
1 answer
195 views

### Real representation versus communication complexity

Suppose that Alice and Bob communicate to compute a function $f:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$. Does the minimal degree of a real polynomial/rational representation of $f$ play a role for ...
• 12.9k
2 votes
0 answers
93 views

### Subtle part of seeing $C(F) \geq \chi(f)$

This question is certainly below research level, however I figured I would get the best answer here. I just started learning about computational complexity (from Arora and Barak) and I have a ...
• 251
2 votes
0 answers
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
2 votes
0 answers
130 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 ...
• 643
2 votes
0 answers
79 views

• 123
1 vote
1 answer
174 views

• 113
1 vote
1 answer
82 views

### Matrix rank approximation

I am aware of the problem of low rank approximation of matrices which has been studied in various models of computation. My question is the following: What is the status of approximating rank of a ...
• 345
1 vote
0 answers
18 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 ...
1 vote
0 answers
66 views

### How to formulate the log-rank conjecture for non-boolean functions?

The log-rank conjecture states that there is a constant $C$ such that for every two-party Boolean function $f$ it holds: $D(f) = O((\log \text{rank} (f))^C)$. If $f$ is not a boolean function then ...
• 2,003
1 vote
0 answers
75 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
1 vote
0 answers
50 views

### What is known about simultaneous protocol set disjointness?

Assume that Alice and Bob have sets $A,B\subseteq[n]$ of size $|A|=|B|=k$. In the simultaneous protocol, they both send a message to Carol (that doesn't observe $A$ and $B$) which needs to determine ...
• 11
1 vote
0 answers
46 views

• 11
1 vote
0 answers
407 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
0 answers
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
1 vote
0 answers
96 views

• 12.9k
1 vote
0 answers
156 views

### Distribution attaining minimum discrepancy of disjointness function

Is it true that for the optimal distribution $\nu$ (not necessarily uniform) that attains minimum discrepancy $\mathsf{disc}(\mathsf{DISJ}_n)$ for the disjointness function $\mathsf{DISJ}_n$ we have ...
• 12.9k
0 votes
1 answer
69 views

• 205
0 votes
0 answers
125 views

### Is this graph communication game known?

Let $X_m=[m]=\{0,1,\dots,m-1\}$ and let $Y_m=[2m]\setminus [m]$. Given is a complete bipartite graph $G_m$, with parts $X_m$ and $Y_m$ and edges $\{x,y\}$ for every $x\in X_m$ and $y\in Y_m$. Alice ...
-1 votes
1 answer
254 views

• 11