# 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

131 questions
Filter by
Sorted by
Tagged with
63 views

### Universal Relation

In the paper Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems, the authors consider the universal relation problem in 2-party communication complexity, which is ...
1 vote
38 views

89 views

### Comparative communication complexity?

I was reading the book "Communication Complexity" by Kuschilevitz and Nisan and in Exercise 1.18 they introduce a variant of the normal vanilla 2-person deterministic communication ...
92 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 ...
64 views

212 views

### Expected vs worst-case communication complexity

In the set disjointness problem of 2-party communication complexity, Alice and Bob are both given an $n$-bit string as input; denoted by $X$ for Alice's input, and $Y$ for Bob's input. They need to ...
1 vote
68 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 ...
1 vote
220 views

159 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 ...
107 views

192 views

### Newman's lemma for distributional communication complexity

This may be obvious — sorry if it is. Newman's lemma (Newman91] shows that any public-coin communication protocol to compute a Boolean function $f\colon \{0,1\}^n\times\{0,1\}^n\to\{0,1\}$ can be ...
159 views

### What is the exact communication complexity of subtree disjointness?

A classic textbook example for communication complexity is when A and B both receive a subtree of a an $n$-node tree (that they both know), and they need to output whether their subtrees are disjoint ...
403 views

299 views

### Communication complexity of approximating the size of set intersection

Consider the set-intersection problem: Alice and Bob each get a subset of $\left\{ 1,\ldots, n\right\}$, and they would like to know whether their sets intersect. This is a canonical problem of ...
1 vote
104 views

139 views

### String distance communication complexity

Consider $(\alpha,t)$-String distance where Alice has $x\in\{0,1\}^n$ and Bob has $y\in\{0,1\}^n$ and they have to decide if $(1-\alpha)t\leq|x\oplus y|\leq (1+\alpha)t$ or not when $\alpha\in[0,1)$ ...
592 views

### Compressing information about the halting problem for oracle Turing machines

The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable. More precisely,...
182 views

### Just how bad is the fooling set method in communication complexity?

I know that if we take a random function, it's likely that the maximal fooling set is at most $kn$ for some constant $k$, while the CC is almost $n$. What bound can I get from above on the ...
152 views

### $NotTooManyP^{cc}$ class in communication complexity

Class $P^{cc}$ is class of languages admitting deterministic communication protocol with polylog bits of communication. Class $NP^{cc}$ is class of languages admitting nondeterministic communication ...
383 views

### Set Intersection lower bounds

Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...