Questions tagged [communication-complexity]
Questions about the amount of communication required to compute a function whose input is distributed between two or more parties
67 questions
1
vote
0
answers
95
views
Prove that chromatic number is lower bound of Communication complexity of deciding an edge between two vertices in a graph
The chromatic number $\chi(G)$
of a graph $G$
is the minimum number of colors needed to color the vertices of $G$
so that no two adjacent vertices have the same color.
Consider the following ...
- 641
0
votes
0
answers
54
views
Communication complexity lower bound to determine MEDIAN of 2 sets
I'm doing Ex. 1.6 in Rao et al. Communication Complexity and Applications:
Alice is given a set $X\subseteq [n]$, Bob is given a set $Y\subseteq [n]$, and their goal is to compute the median of the ...
- 641
0
votes
1
answer
126
views
Communication complexity lower bound to differentiate 2 strings
I'm doing ex. 1.4 in Rao et al. Communication Complexity: and Applications:
Let $\mathcal{X}$ be the subset of $\{0, 1\}^n$ such that each element has more $0$s than $1$s.
Let $\mathcal{Y}$ be the ...
- 641
0
votes
1
answer
69
views
Communication complexity of $\text{DISJ}_n$ function
I have encountered this question when reading Razborov's communication complexity survey.
The function $\text{DISJ}_n$ is defined on $\{0, 1\}^n\times \{0, 1\}^n$
as $$\text{DISJ}_n(x, y) = 1 \iff \...
- 641
3
votes
0
answers
40
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
65
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
72
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
49
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
119
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
55
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
97
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
52
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
75
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
198
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
109
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 ...
