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

Filter by
Sorted by
Tagged with
4 votes
0 answers
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 ...
user avatar
  • 51
1 vote
0 answers
38 views

Quantum Communication Complexity Bound on Vector Inner Product

Say Alice has a (complex) vector $a\in\mathbb{C}^d$, and interacts with Bob in a quantum communication protocol (sending qubits back and forth). At the end of the protocol, Bob produces a guess $b\in\...
user avatar
  • 11
2 votes
1 answer
122 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 ...
user avatar
5 votes
1 answer
205 views

Complexity of Yao's tiling number?

In communication complexity, we encounter the complexity measure $\chi(f)$ for $f : \{0,1\}^{2n} \to \{0,1\}$ which is the minimal number of $f$-monochromatic rectangles needed to tile the $2^n \times ...
user avatar
4 votes
1 answer
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 ...
user avatar
2 votes
0 answers
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 ...
user avatar
0 votes
1 answer
64 views

Deterministic communication complexity of refinement

A partition of $[n]$ is a collection $\mathcal{P}$ of non-empty subsets of $[n]$ such that for each $i \in [n]$ there is a unique $P \in \mathcal{P}$ with $i \in P$. For partitions $\mathcal{P}, \...
user avatar
1 vote
0 answers
70 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 ...
user avatar
  • 199
0 votes
0 answers
102 views

Using the probabilistic method to fill the gaps in a proof of set disjointness

In the 2-party $k$-sparse set disjointness problem, we have a set $U$ of size $n$ and there are two parties: Alice, who gets a set $X \subseteq U$ and Bob who gets a string $Y \subseteq U$, and it ...
user avatar
  • 51
1 vote
1 answer
111 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 ...
user avatar
  • 239
1 vote
0 answers
113 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 ...
user avatar
3 votes
0 answers
82 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 (...
user avatar
1 vote
1 answer
138 views

Average-case randomized communication complexity in the small-advantage regime

Let $f\colon \{0, 1\}^n \times \{0, 1\}^n \to \{0, 1\}$. I'm interested in randomized communication protocols $\pi$ that compute $f$ in the weak sense that $$ \Pr_{x, y}\left[\Pr_r[\pi(x, y, r) = f(x, ...
user avatar
  • 1,733
13 votes
2 answers
589 views

One-way randomized communication complexity of Greater-Than

Let $\mathrm{GT}_n:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ be the greater than function: $\mathrm{GT}_n(x,y)=1$ exactly when the positive integer whose binary representation is $x$ is greater than the ...
user avatar
1 vote
1 answer
88 views

Composition theorem for randomized communication complexity

I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find $$ R_{1/4} (f \circ ...
user avatar
  • 113
3 votes
1 answer
91 views

Lipschitz composable compressor

Def. We call $C: \mathbb R^d \to \mathbb R^d$ a $\delta$-compressor (or contractor) if for all $x$ $$\|C(x) - x\|^2 \le (1 - \delta) \|x\|^2$$ Intuitively, $C(x)$ is not too far from $x$. Note that $\...
user avatar
  • 191
7 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
0 answers
220 views

communication complexity lower bound for computing median

In the textbook by Kushilevitz/Nisan, they give an $O(\log n)$-bit protocol for computing the median in the standard 2-party model of communication complexity, where Alice is given a set $X \subseteq [...
user avatar
  • 11
2 votes
0 answers
100 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 ...
user avatar
1 vote
0 answers
239 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 ...
user avatar
1 vote
0 answers
70 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 ...
user avatar
  • 123
2 votes
0 answers
116 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 ...
user avatar
  • 633
1 vote
0 answers
90 views

How does Best Partition Communication Complexity behave under input transformations?

I'm looking for references about the behavior of communication complexity under input transformations. A specific toy example of the kind of question I'm interested in is the following. Let $f(x_1,......
user avatar
  • 1,052
2 votes
1 answer
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 ...
user avatar
4 votes
0 answers
107 views

Expected vs actual amount of information leaked by an $l$-bits message

Say we have a random variable $X$ that contains $k$ bits of information, and a message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $...
user avatar
3 votes
1 answer
135 views

Estimating inner product over $[r]^d$

Alice has a vector $x \in [r]^d$ and Bob has $y \in [r]^d$, where $[r] \stackrel{\rm def}{=} \{0,1,\dots,r\}$. Alice send a message $M(x)$ to Bob and Bob wants to estimate the inner product $\left<...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 4,331
4 votes
0 answers
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 ...
user avatar
  • 13.5k
6 votes
1 answer
403 views

Combination of Disjointness and Gap Hamming Distance communication complexity

Consider the two player constant-round communication problems: Gap Hamming Distance $\Delta(a,b)$ where Alice and Bob each has an $n$-length bit string $a$ and $b$ respectively. YES case: $\Delta(a,...
user avatar
  • 239
-1 votes
1 answer
199 views

Reducing disjoint or indexing or inner-product problem to s-t connectivity problem in directed graph

I am asked to prove that an O(1)-pass randomized streaming algorithm that solves s-t connectivity problem in a simple directed graph $G=(V,E)$ with $|V|=n$ vertices, with sucess possibility $>\frac{...
user avatar
  • 13
8 votes
2 answers
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 ...
user avatar
  • 5,055
1 vote
1 answer
104 views

Using a probability distribution in the fooling set technique for communication complexity

I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition: Let $\mu$ be a probability distribution of $X\...
user avatar
  • 123
-1 votes
1 answer
74 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 ...
user avatar
  • 11
6 votes
1 answer
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 ...
user avatar
1 vote
0 answers
49 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?
user avatar
1 vote
0 answers
152 views

On the log rank conjecture

We think the log rank conjecture is true over $\{0,1\}$ real matrices and over any fixed alphabet matrix. What is the fastest function $f(r)$ of rank $r$ such that the log rank conjecture over $\{0,1\...
user avatar
  • 12.5k
0 votes
1 answer
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)$ ...
user avatar
  • 12.5k
12 votes
1 answer
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,...
user avatar
4 votes
0 answers
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
15 votes
0 answers
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 ...
user avatar
  • 1,107
6 votes
2 answers
484 views

How powerful is $ACC^0$ circuit class in average case?

We know that $NEXP$ is not in $ACC^0$ . Does the result that $NEXP$ is not in $ACC^0$ also hold in average case? That is given a boolean function in $NEXP$ is it known that for every input length $...
user avatar
  • 12.5k
0 votes
0 answers
123 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 ...
user avatar
8 votes
1 answer
272 views

Is there a name for this concept in Communication Complexity?

Let Alice and Bob compute boolean function $f(x_1,\dots,x_{2n})$. Select a random subset $\mathcal I\subseteq\{1,\dots,2n\}$ of cardinality $n$ and let $\mathcal J=\{1,\dots,2n\}\backslash\mathcal I$....
user avatar
  • 12.5k
9 votes
1 answer
297 views

Regular languages and constant communication complexity

Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$. I'm searching for a reference for: Proposition. $L$ is regular iff ...
user avatar
3 votes
0 answers
132 views

Evaluating boolean formula without knowing all values

I am looking for research approaches for the following problem: assume we have a set of $m$ computers, each carries a bit, and a Boolean formula $\varphi$ over those $m$ variables. The computers are ...
user avatar
  • 31
4 votes
0 answers
126 views

Communication complexity protocols depending on inputs

Classical communication complexity requires one protocol (binary tree with edges labeled by bits Alice and Bob send) to solve the problem for every pair of inputs. What if we allow Alice and Bob to ...
user avatar
  • 251
1 vote
0 answers
152 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 ...
user avatar
  • 12.5k
3 votes
2 answers
360 views

Methods for proving deterministic communication complexity lower bounds

I am familiar with the classic techniques for proving deterministic communication complexity lower bounds for boolean functions in the 2-party model: To the best of my knowledge, these are fooling ...
user avatar