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
1
vote
0
answers
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 ...
- 11
7
votes
0
answers
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 ...
- 576
0
votes
0
answers
31
views
Natural communication problems that are hard only for number-in-hand protocols?
I am looking for tools to lower bound the deterministic, blackboard, number-in-hand communication complexity of a certain function which is roughly speaking $f : \{0,1\}^k \times \ldots \times \{0,1\}^...
- 205
1
vote
0
answers
64
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 ...
- 1,973
1
vote
1
answer
115
views
Communication complexity of equality on graphs
I came upon a nice observation in communication complexity, and I was wondering if it was already known.
Consider the following variant of the equality problem: There is a fixed graph $G$ that is ...
- 5,350
3
votes
1
answer
95
views
What are the up-to-date results on explicit lower bounds for $\Sigma_2$ communication complexity?
What are the best polylogarithmic lower bounds known for $\Sigma_2$-communication complexity on an explicit function? Are there any known candidate functions for $O(n^\epsilon)$ communication ...
- 241
4
votes
0
answers
127
views
Boolean matrix $M$ with Boolean rank $r$ but real rank $2^r$
$\newcommand{\F}{\mathbb{F}}\newcommand{\R}{\mathbb{R}}$
Question is in the title basically: does there exist a Boolean matrix $M$ where $\operatorname{rank}_{\F_2}(M)=r$ but $\operatorname{rank}_{\R}(...
- 51
1
vote
0
answers
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 ...
- 51
0
votes
1
answer
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, ...
5
votes
1
answer
158
views
Natural hard communication problems with both nondeterministic and co-nondeterministic complexity of $\sqrt{n}$?
I'm trying to lower bound the worst-case deterministic communication complexity of some special class of functions on $n$ variables, and I've shown that for every function $f$ in the class: $N^1(f) = ...
- 205
4
votes
1
answer
300
views
Randomized communication complexity of or-of-equalities
Is there a reference for a randomized communication lower bound for the following problem: $\textsf{Or-of-Equalities} : \{0,1\}^{n^2} \times \{0,1\}^{n^2} \to \{0,1\}$ defined by $f(x,y)=1$ iff there ...
- 235
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
4
votes
0
answers
81
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 ...
- 41
1
vote
0
answers
45
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\...
- 11
2
votes
1
answer
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 ...
- 251
5
votes
1
answer
211
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 ...
- 251
4
votes
1
answer
97
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 ...
- 251
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
0
votes
1
answer
68
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}, \...
- 921
1
vote
0
answers
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
1
answer
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
0
answers
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 ...
- 11
3
votes
0
answers
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 (...
- 31
1
vote
1
answer
164
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, ...
- 1,733
13
votes
2
answers
869
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 ...
- 18.1k
1
vote
1
answer
100
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 ...
- 113
3
votes
1
answer
98
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 $\...
- 201
7
votes
1
answer
249
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
1
answer
76
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
363
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 [...
- 11
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
1
vote
0
answers
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 ...
- 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
2
votes
0
answers
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 ...
- 643
1
vote
0
answers
92
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,......
- 1,062
2
votes
1
answer
175
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
4
votes
0
answers
114
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 $...
- 223
3
votes
1
answer
139
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<...
- 223
4
votes
1
answer
234
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 ...
- 4,451
4
votes
0
answers
169
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 ...
- 13.9k
6
votes
1
answer
416
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,...
-1
votes
1
answer
249
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{...
- 13
8
votes
2
answers
392
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 ...
- 5,350
1
vote
1
answer
115
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\...
- 123
-1
votes
1
answer
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 ...
- 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 ...
- 345
1
vote
0
answers
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?
- 891
1
vote
0
answers
157
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\...
- 12.8k
0
votes
1
answer
144
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)$ ...
- 12.8k
12
votes
1
answer
644
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,...
- 221