Questions tagged [communication-complexity]
Questions about the amount of communication required to compute a function whose input is distributed between two or more parties
63 questions
3
votes
0
answers
23
views
Communication complexity of testing balancedness of a Boolean polynomial
The problem I consider is the following: given the $2^n$ coefficients of a Boolean polynomial $f : \{0, 1\}^n \rightarrow \{0, 1\}$, determine if $f$ is balanced namely if the truth table of $f$ ...
1
vote
0
answers
47
views
Communication Complexity of "2-Bit"
[For context, I'm trying to work through the derivation of Lemma 2.1 (2-Bit) here, https://users.cs.utah.edu/~jeffp/papers/multiCC-soda12.pdf. ]
The '2-Bit' setup is that Alice draws a bit-string of ...
- 46
1
vote
0
answers
44
views
Why one-sided-error equality problem communication complexity is at least O(n)
I'm trying to solve an exercise from "Algorithmics for hard problems" but I have no idea how to solve it. First the definition of one-sided-error Monte Carlo algorithm is a little different ...
0
votes
1
answer
24
views
When does augmented indexing become easy?
Consider the following problem in 2-party communication complexity, where Alice sends a single message to Bob who must compute the output.
Alice gets as input a bit vector $X=(x_1,...,x_N)$, for some ...
- 111
1
vote
1
answer
56
views
Nondeterministic Communication Complexity - How to Calculate it from Communication Matrix?
I have been wracking my head around the understanding on how to calculate $N_{1}(f)$ and $N_{0}(f)$ from the communication matrix.
Definitions:
$N_{1}(f)$ = least cost of non-deterministic protocol ...
- 93
0
votes
1
answer
25
views
How to translate the problem into a Communication Matrix?
Description of the problem:
Alice and Bob are both given as input the same graph and vertex $x$ and $y$ respectively. In the graph there are no self-loops and the given vertex can be the same.
Prove ...
- 93
1
vote
1
answer
57
views
Communication complexity of Dyck language
I've been reading papers on streaming algorithms and ran across the following question which I haven't been able to answer: Consider the Dyck language $Dyck(2)$ over the alphabet $A = \{(,),[,]\}$ and ...
- 11
2
votes
0
answers
30
views
Understanding the proof of a property of 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 ...
- 21
1
vote
1
answer
48
views
Can a static pre-shared database reduce communication size?
Is the problem of communication with a pre-shared database studied? If yes, what field studies it, or which researchers work on it?
Let there be two parties that want to share multiple yet-to-be-...
-3
votes
1
answer
157
views
Identify the missing number in a set given its superset
Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number?
That is,
B’ = B \ {y}, for some unknown element y
B = A \ {x}, for ...
- 1
1
vote
0
answers
79
views
Communication complexity of index problem with large domains
In the standard definition of the Index problem in one-way 2-party communication complexity, there are two players, Alice and Bob. Alice gets a binary input vector $x$ of length $n$ and Bob gets an ...
2
votes
1
answer
86
views
The universal relation problem in communication complexity
In the universal relation $UR_n$ problem [1] of communication complexity, there are two players Alice and Bob. Alice gets a string $x \in \{0,1\}^n$, Bob gets a string $y \in \{0,1\}^n$ with the ...
1
vote
0
answers
22
views
Complexity classes and "local pre-processing"
My question
I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...
- 131
1
vote
1
answer
76
views
Las Vegas vs Deterministic in one-way communication complexity
I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte ...
- 13
2
votes
1
answer
33
views
Why is the communication complexity of f on disjunction of x and y is bounded above by 2D(f)
Let f be a Boolean function on n variables. Let $DC(g)$ and $D(g)$ denote the deterministic communication complexity and the decision tree complexity of $g$. Why is the following inequality true:
$$DC(...
- 991
2
votes
1
answer
227
views
Deriving a lower bound on the conditional entropy, conditioned on an event
I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
- 23
1
vote
1
answer
75
views
Communication complexity of equality gap problem
I'm interested to know what is the biggest known $0\le \epsilon\le 1$ such that the $gap-EQUALITY$ problem that is defined by:
$$f_\text{GEQ}(x,y)=\cases{1&$x=y$\\0 & $x$ and $y$ differ in at ...
- 11.7k
1
vote
2
answers
704
views
Check array in linear time with a constant space complexity
Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false.
E.g.
...
- 113
2
votes
1
answer
96
views
Complexity of two-party maximum
Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$),...
- 21
2
votes
1
answer
313
views
The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?
I'm following along the examples in https://people.csail.mit.edu/rrw/6.045-2020/note-cc.pdf
and in specifically the following text:
What’s a good protocol for computing MAJORITY? The natural thing to ...
- 75
4
votes
2
answers
190
views
Does O(1) communication complexity imply that a language is regular?
Let's say that we have a function $g(i,j)$, which is an arbitrary boolean-valued function over $i,j \in \{a,b\}^*$, such that $|i| = |j| = m.$ Moreover, we can also say that $g$ has communication ...
1
vote
0
answers
100
views
A communication problem about graphs
An undirected graph on $n$ vertices and $n-1$ edges $G = (V,E)$ is partitioned between two players $A$ and $B$ such that $A$ knows $(V,E_A)$, $B$ knows $(V,E_B)$ and $E_A \dot\cup E_B = E$.
Initially, ...
- 151
0
votes
1
answer
99
views
Is unary machine code a concept?
Please assume for the sake of this session that humans can fluently read and understand machine languages and time isn't a problem in that regard.
I, not a computer scientist, would at least theorize ...
- 3
0
votes
0
answers
33
views
What is the optimal combination of transducers with limited capabilities to a more powerful transducer?
Assume we have a number of transducers with limited information processing capabilities. Are there theoretical results (proofs) on how these transducers can be combined by some sort of communication ...
1
vote
1
answer
95
views
Communication Complexity for Product Distributions
In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $\Omega(n)$. Surprisingly, today I discovered (if I understood correctly) ...
- 289
1
vote
1
answer
107
views
The communication complexity of the distance between two strings
Assume that Alice and Bob are respectively given two strings $x \in \{0,1\}^n$ and $y \in \{0,1\}^n$ such that the hamming distance between $x$ and $y$ is either $> n/2+\sqrt{n}$ or $< n/2-\sqrt{...
- 151
1
vote
0
answers
96
views
Decomposition of Mutual Information [closed]
I came across a book where the author uses the following property of mutual information:
Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable.
$$
(1)\ \ ...
- 33
3
votes
1
answer
92
views
Upper bound for set disjointness under product distributions
For the set disjointness problem in the 2-party model of communication complexity, Alice is given an input $X$ and Bob is given input $Y$, $X$ and $Y$ are $n$-length bitstrings (sampled from some ...
3
votes
2
answers
268
views
Lower bound of disjointness by discrepancy?
I need to show that $Disc_\mu(Disj) \geq \frac{1}{2n+1}$ for any distribution $\mu: \{0,1\}^n \times \{0,1\}^n \to [0,1]$.
Disjointness is defined as
$Disj(X,Y)=\left\{ \begin{array}[ll]+1 & \...
- 35
0
votes
1
answer
21
views
Can a transcript change dependent random variables into independent variables?
Let's say $X, Y$ are dependent random variables. Can I find an example such that for a transcript $t$ conditioned on a communication protocol $\Pi=t$, the variables become independent?
- 35
0
votes
0
answers
266
views
utilization of bitmap protocol
I am curious about utilization calculation in the bitmap protocol. especially if there's a difference between if only station 0 wants to broadcast(and the others doesn't) or only some other station ...
- 101
5
votes
2
answers
2k
views
The Clique vs. Independent Set Problem
Suppose you have an undirected graph $G = (V, E)$, known to both Alice and Bob, Alice gets an independent set of $G$. Bob gets a Clique $B ⊆ V$.
Is there any algorithm in $O(\log^2 n)$ bits that ...
- 221
0
votes
0
answers
39
views
Maximal number of parallel cellular calls with no adjacent cells in a hexagonal setting
Is it possible to find an optimization to the following theoretical case?
Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are ...
- 1
1
vote
1
answer
254
views
Communication complexity: fooling set bound for inner product function
I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound ...
- 249
1
vote
1
answer
167
views
Complexity of sending an $n$-bit string
Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be ...
- 151
1
vote
1
answer
191
views
Randomized communication complexity of indexing
The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as
$$\mathrm{INDEX}(x,i)=x_i,$$
where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\...
- 994
2
votes
2
answers
819
views
Lower Bounds for the Set Disjointness Problem
Consider the set disjointness problem. Alice and Bob hold n-bit strings $a$ and $b$ respectively.
They would like to compute the function
$$
\text{Dis}(a,b) =
\begin{cases}
0 &\text{...
- 289
4
votes
1
answer
98
views
Compute the union of two sets between two endpoints minimizing communication complexity
I have two endpoints, $a$ and $b$, that can communicate through a channel. $a$ is storing a set of fixed-length strings $A = \{a_1, \ldots, a_{N_A}\}$, and $b$ is storing another set of fixed-length ...
- 205
1
vote
1
answer
287
views
Communication complexity of string matching
let us consider Alice and Bob communicate over channel bit by bit. They have one string over $\{0,1\}^{*}$. Let $x$ (uniformly at random) be the string that Bob have and $y$ be the string that Alice ...
- 1,205
4
votes
1
answer
379
views
The communication complexity of Hamming distance mod $4$
If Alice and Bob each have a bit string of length $n$, what is the randomized communication complexity (either one or two-way) of computing the Hamming distance mod $4$? It seems this is hard to ...
- 1,036
2
votes
2
answers
348
views
Protocols for "almost equality" with one-sided error
In the well-known communication task EQUALITY, Alice has a string $x$ of $n$ bits, Bob has a string $y$ of $n$ bits, and their task is to determine whether $x = y$. In the public coin model, there is ...
- 279k
2
votes
1
answer
470
views
Theory of message complexity analysis of distributed systems
Inspired by this post, I thought it would be a good idea to ask an analogous question in the context of distributed systems -
While most of us are familiar with the notion of Time Complexity as a ...
- 142
5
votes
1
answer
57
views
Worst known case for log rank conjecture
The log rank conjecture states that there is some universal constant $c > 0$ so that
$$CC(f) = O(\log^c \text{rk}\,(M_f))$$
where $f : X \times Y \to \{0, 1\}$ is a boolean function, $CC$ denotes ...
- 473
2
votes
0
answers
31
views
Combinatorial model for multiparty communication complexity
Brief introduction:
In two-party communication complexity, as presented by Yao in 1979, we model protocols as binary trees whose internal nodes are labeled by either Alice or Bob, and the leaves are ...
- 136
4
votes
0
answers
95
views
Direct sum non-deterministic protocol for the non-equality function
Brief introduction:
Let $n \in \mathbb N$. The non-equality function, denoted $ NE : \{0,1\}^n \times \{0,1\}^n \to \{0,1\} $ is defined as follows:
\begin{align}
\forall x,y\in \{0,1\}^n \;\;\; NE(...
- 136
3
votes
1
answer
115
views
Randomized and Deterministic Communication Complexity of a function
I have a problem I'm trying to answer for my homework. The question is:
Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $...
- 31
-1
votes
1
answer
140
views
Communication Complexity and Prefix Codes [closed]
I need an advice.
There is in section "V. CONCLUDING REMARKS" of the paper [1],
a term that only the autho's paper use: "PREFIX CODING COMMUNICATION".
I googled the expression and the only result ...
- 179
2
votes
1
answer
297
views
Example of reduction in communication complexity
Let us assume the standard situation in communication complexity with two players $P_1,P_2.$
We have a function $f:[n] \times [n] \mapsto \{0,1\}$ that both players known in advance. They wish to ...
- 2,460
1
vote
1
answer
125
views
What is a "geometric rectangle"?
In the [Kushilevitz and Nisan 2006, P.10] they give an exercise which says as following:
Exercise 1.18: Let $X=Y=\{1,\ldots,n\}$. A geometric rectangle is a set of the form $\{(x,y)|x_{\min} \leq x ...
- 759
2
votes
1
answer
96
views
About the definition of "differential privacy" in communication complexity
In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense.
So the two parties $A$ and $B$ draw two strings $X$ ...
- 1,165