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

120 questions
Filter by
Sorted by
Tagged with
102 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 ...
60 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 (...
104 views

84 views

99 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 ...
162 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 ...
66 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 ...
104 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 ...
80 views

124 views

161 views

72 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 ...
185 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 ...
46 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?
150 views

121 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 ...
270 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$....
263 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 ...
131 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 ...
123 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 ...
149 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 ...
338 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 ...
169 views

Nondeterministic communication complexity of Hamming distance

It is something that I think should be known: what is nondeterministic communication complexity of following task: is $H(x,y) \geq k$? There is an obvious upper bound $k \log(n)$. I would expect ...
961 views

149 views

Problems still “hard” in the SMP/Referee model with shared randomness?

In the referee (SMP: Simultaneous Message Passing) model introduced by Yao (see e.g. [1]), Alice and Bob have respectively inputs $x\in X$ and $y\in Y$, and wish to communicate with a third-party, the ...
73 views

Communication complexity of edit resilient synchronization

Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ...
125 views

Lower Bound for Nonzero Terms of a Polynomial Fully Sensitive at 0

Every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be uniquely represented as a multilinear polynomial $p=\sum_{S\subseteq [n]}c_S \chi_s$ where $\chi_s=\prod_{i\in S}x_i$. A boolean function is ...
348 views

Gap-Hamming with different “threshold” (i.e., not $n/2$)

Following a previous question, I'm trying to get a better understanding of the parameters at play in $\textsf{Gap-Hamming}$. In the "standard" setting, we have $x,y\in\{0,1\}^n$ and the partial ...
191 views

One way communication complexity of multi exact matching

Let Alice have $n$ binary strings, each of length $n$ and let Bob have one binary string of length $n$. Bob has to output $1$ if his string matches any of Alice's exactly and $0$ otherwise. Clearly ...
The $\textsf{GapHammingDistance}$ problem over $\{0,1\}^n$ is defined as follows: Alice (resp. Bob) is given an input $x\in\{0,1\}^n$ (resp, $y\in\{0,1\}^n$), under the promise that their Hamming ...