Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

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
0 votes
0 answers
63 views

On $PP$ vs $\oplus P$ in CC

In communication complexity is it known that the classes $PP^{cc}$ and $\oplus P^{cc}$ satisfy $PP^{cc}\not\subseteq\oplus P^{cc}$?
Turbo's user avatar
  • 12.9k
1 vote
0 answers
19 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 ...
user4594525's user avatar
7 votes
0 answers
117 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 ...
Naysh's user avatar
  • 686
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\}^...
Clay Thomas's user avatar
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 ...
Alexey Milovanov's user avatar
1 vote
1 answer
122 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 ...
Or Meir's user avatar
  • 5,615
3 votes
1 answer
98 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 ...
Stefan G.'s user avatar
  • 241
4 votes
0 answers
135 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}(...
Ash's user avatar
  • 49
1 vote
0 answers
76 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 ...
Ash's user avatar
  • 49
0 votes
1 answer
69 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, ...
polar_bear_cheese's user avatar
5 votes
1 answer
160 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) = ...
Clay Thomas's user avatar
4 votes
1 answer
317 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 ...
Noah Singer's user avatar
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 ...
John's user avatar
  • 11
4 votes
0 answers
84 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 ...
Theo's user avatar
  • 41
1 vote
0 answers
46 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\...
Yang's user avatar
  • 11
2 votes
1 answer
148 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 ...
user101010's user avatar
5 votes
1 answer
213 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 ...
user101010's user avatar
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 ...
user101010's user avatar
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 ...
user101010's user avatar
0 votes
1 answer
70 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}, \...
user1868607's user avatar
  • 1,019
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 ...
Nav89's user avatar
  • 209
1 vote
1 answer
118 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 ...
polar_bear_cheese's user avatar
1 vote
0 answers
127 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 ...
Koko Nanahji's user avatar
3 votes
0 answers
169 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 (...
cc_student's user avatar
2 votes
1 answer
176 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, ...
William Hoza's user avatar
  • 1,743
13 votes
2 answers
1k 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 ...
Sasho Nikolov's user avatar
1 vote
1 answer
103 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 ...
exteral's user avatar
  • 113
3 votes
1 answer
99 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 $\...
Dmitry's user avatar
  • 201
7 votes
1 answer
260 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 ...
cstheory_student1's user avatar
1 vote
1 answer
83 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 ...
withhighprob's user avatar
1 vote
0 answers
442 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 [...
JohnDoe's user avatar
  • 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 ...
Dustin Wehr's user avatar
1 vote
0 answers
417 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 ...
Lars Ericson's user avatar
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 ...
NNN's user avatar
  • 123
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 ...
exfret's user avatar
  • 643
1 vote
0 answers
97 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,......
verifying's user avatar
  • 1,072
3 votes
1 answer
183 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 ...
user135743's user avatar
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 $...
Dawei Huang's user avatar
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<...
Dawei Huang's user avatar
5 votes
1 answer
259 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 ...
Clement C.'s user avatar
  • 4,471
4 votes
0 answers
170 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 ...
domotorp's user avatar
  • 14k
6 votes
1 answer
422 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,...
polar_bear_cheese's user avatar
-1 votes
1 answer
255 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{...
Naketo's user avatar
  • 13
8 votes
2 answers
429 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 ...
Or Meir's user avatar
  • 5,615
1 vote
1 answer
123 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\...
NNN's user avatar
  • 123
-1 votes
1 answer
79 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 ...
JohnDoe's 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 ...
withhighprob's user avatar
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?
ivmihajlin's user avatar
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\...
Turbo's user avatar
  • 12.9k
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)$ ...
Turbo's user avatar
  • 12.9k