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
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
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
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 ...
D.W.♦
- 166k
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
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.
...
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-...
D.W.♦
- 166k
-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 ...
- 39.1k
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 ...
- 279k
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$),...
CommunityBot
- 1
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 ...
- 279k
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(...
- 279k
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$ ...
- 8,342
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 ...
D.W.♦
- 166k
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 ...
- 279k
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 ...
- 279k
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{...
CommunityBot
- 1
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 ...
- 279k
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 ...
D.W.♦
- 166k
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) ...
- 279k
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 ...
- 279k
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 & \...
- 39.1k
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?
D.W.♦
- 166k
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 ...
- 66
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 ...
- 5,037
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 ...
- 279k
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 ...
- 279k
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 $\...
- 279k
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{...
- 279k
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 ...
D.W.♦
- 166k
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 ...
- 13.6k
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 ...
- 279k
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 ...
D.W.♦
- 166k
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 ...
- 72.9k
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
5
votes
1
answer
76
views
Do correlated inputs imply existence of efficient communication protocols?
Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such ...
- 279k
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 $...
- 279k
6
votes
1
answer
300
views
A Myhill-Nerode type characterization of the regular languages using fooling sets?
Ultimately, my question is whether it's possible to exactly characterize the regular languages in terms of fooling sets. To help explain my motivation for asking this, here's a quick exposition.
Let $...
- 279k
-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 ...
- 279k