Skip to main content
6 votes
Accepted

The Clique vs. Independent Set Problem

The two players construct a sequence $V_0 \supset V_1 \supset \cdots \supset V_m$ of sets of vertices such that: $V_0$ consists of all vertices in the graph. $|V_{i+1}| \leq (|V_i|+1)/2$. $V_i \...
Yuval Filmus's user avatar
4 votes
Accepted

The communication complexity of Hamming distance mod $4$

Consider the following task $f$: Given $x,y \in \{0,1\}^n$, Alice and Bob need to determine whether $d(x,y) \bmod{4} \in \{0,1\}$, where $d(x,y)$ is the Hamming distance between $x$ and $y$. Let $M_f$...
Yuval Filmus's user avatar
4 votes
Accepted

Worst known case for log rank conjecture

The function is described in a footnote in Nisan and Wigderson's paper On rank vs. communication complexity. It is $$ E(z_1 \dots z_6) = \sum_i z_i - \sum_{ij} z_{i}z_{j} + \\z_1z_3z_4 + z_1z_2z_5 + ...
Yuval Filmus's user avatar
4 votes

The Clique vs. Independent Set Problem

The $O(\log n)$ rounds comes from the fact that we are doing a binary search: If the algorithm fails to terminate, then either Alice or Bob share a vertex v. If Alice shares $v$, then $v$ has ...
James Bailey's user avatar
3 votes
Accepted

Check array in linear time with a constant space complexity

The problem does not have any $O(n)$ time algorithm. Note that it is easy to check in linear time if all the elements in the array are the same or not. However, to check if all the elements are ...
Inuyasha Yagami's user avatar
3 votes

Compute the union of two sets between two endpoints minimizing communication complexity

You can do this with $O(K \log N)$ bits of communication on average, where $K$ is the size of $|(A\setminus B) \cup (B\setminus A)|$, assuming you are willing to use a non-interactive protocol and are ...
D.W.'s user avatar
  • 162k
3 votes

Communication complexity of string matching

By simply exchanging random indices you cannot hope to do better than $\Omega(n)$ communication if you want constant error probability. If the strings differ in only a single bit, and you exchange $k$ ...
Ariel's user avatar
  • 13.4k
3 votes
Accepted

The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?

Yes it's perfectly fine for one player to send multiple bits while the other waits. In fact, "the" trivial upper bound on communication complexity is having one party send its input to the ...
integrator's user avatar
  • 1,110
3 votes

Does O(1) communication complexity imply that a language is regular?

No. Let $L_0$ be a context-free language, say the language of matched parentheses, $L_1 = \Sigma^* \setminus L_0$, and $$L = \{ij \mid b \in \{0,1\}, i \in L_b, j \in L_b, |i|=|j|\}.$$ Then $L$ is ...
D.W.'s user avatar
  • 162k
2 votes

Theory of message complexity analysis of distributed systems

S. Arora, B. Barak, Computational Complexity Modern Approach, Chapter 13 is a good introductory resource to this topic: Communication complexity concerns the following scenario. There are two ...
fade2black's user avatar
  • 9,847
2 votes

Protocols for "almost equality" with one-sided error

Here are two solutions. In both cases, the inputs are $x,y \in \{0,1\}^n$, and we are interested in checking whether the Hamming distance between $x$ and $y$ is at most $k$ or not. Solution 1 (D.W.): ...
Yuval Filmus's user avatar
2 votes
Accepted

Communication Complexity for Product Distributions

Set disjointness is easier for product distributions since the hard distribution for set disjointness is very far from being a product distribution. What do we require from a hard distribution $(X,Y)$ ...
Yuval Filmus's user avatar
2 votes
Accepted

Why is the communication complexity of f on disjunction of x and y is bounded above by 2D(f)

Given a decision tree for $f(z)$, we can simulate it in the communication model in the following way: whenever the decision tree queries $z_i$, Alice sends $x_i$ and Bob sends $y_i$, and now both of ...
Yuval Filmus's user avatar
2 votes
Accepted

Communication complexity of equality gap problem

When $\epsilon < 1/2$, you can pick a code with exponentially many codewords and minimum distance $\epsilon n$. If the inputs are promised to be in the code, your problem becomes EQUALITY, and so ...
Yuval Filmus's user avatar
2 votes

Complexity of two-party maximum

Write $x = (x_h,x_l)$ and $y = (y_h,y_l)$, where $x_h,y_h$ are the high-order parts. Alice sends $x_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x_h > ...
Yuval Filmus's user avatar
1 vote

When does augmented indexing become easy?

I can answer my own question: Alice just sends the parity of her input to Bob, and from this, Bob can compute the answer, so there is no nontrivial lower bound.
CCStudent's user avatar
  • 111
1 vote
Accepted

Nondeterministic Communication Complexity - How to Calculate it from Communication Matrix?

Here are the $\log n + 1$ rectanges that cover all 0s in the case of the Equality function: for all $i \in [\log n]$ and $b \in \{0, 1\}$, there is a rectangle $$ \{ (x,y) : x_i = b, y_i \neq b \} = \...
Yuval Filmus's user avatar
1 vote
Accepted

How to translate the problem into a Communication Matrix?

As @jschnei has mentioned in the comment, the answer is: The communication matrix has rows indexed by Alice's inputs, columns indexed by Bob's input, and value f(x, y) at the cell in the row ...
Meki21's user avatar
  • 93
1 vote

Communication complexity of Dyck language

TL;DR: $n \le C(f) \le n+1$. We can easily prove that $C(f) \ge n$. Consider the set of $x \in \{(,[\}^n$. There are $2^n$ such $x$-values. Each matches a different set of $y$-values. So, you need ...
D.W.'s user avatar
  • 162k
1 vote

Does O(1) communication complexity imply that a language is regular?

Let $L'$ be an arbitrary language, and consider $$ L = \{ \Sigma^{|x|} x : x \in L' \}. $$ Then $L$ has roughly the same complexity as $L'$, but it has communication complexity $1$.
Yuval Filmus's user avatar
1 vote

The communication complexity of the distance between two strings

Suppose that the Hamming distance between $x$ and $y$ is $n/2 - \sqrt{n}$. Suppose that you sample $m$ indices with replacement, and let $S$ be the number of indices on which $x$ and $y$ disagree. ...
Yuval Filmus's user avatar
1 vote
Accepted

Upper bound for set disjointness under product distributions

During the first phase of the algorithm, the players zoom in on a high-entropy coordinate. They exchange $O(1)$ bits, and stop at each step with probability $\Omega(\epsilon^2/\log^2(1/\epsilon))$ (...
Yuval Filmus's user avatar
1 vote
Accepted

Lower bound of disjointness by discrepancy?

Let me clarify the question first. $\mu$ is a probability distribution over the sample space $S=\{0,1\}^n \times \{0,1\}^n$. A combinatorial rectangle (or just rectangle) $R$ is a subset of $S$ of ...
John L.'s user avatar
  • 39k
1 vote

Lower bound of disjointness by discrepancy?

You asked two questions. I'll answer the second. A rectangle is a set $R$ of the form $$R = \{(x_1,\dots,x_n) : \ell_1 \le x_1 \le u_1, \dots, \ell_n \le x_n \le u_n\}$$ for some $\ell_1,\dots,\...
D.W.'s user avatar
  • 162k
1 vote
Accepted

Can a transcript change dependent random variables into independent variables?

Yes. Consider the following protocol. Alice flips a coin, and sets $X$ and $Y$ to be equal to the outcome of the coin flip. She then sends $X,Y$ to Bob. Note that the transcript will include the ...
D.W.'s user avatar
  • 162k
1 vote

Complexity of sending an $n$-bit string

You haven't defined when a randomized protocol is declared to be successful, so I will assume that at the end of the protocol, Bob tells a judge what he thinks the message is, and we want that for ...
Yuval Filmus's user avatar
1 vote
Accepted

Randomized communication complexity of indexing

It is known that the randomized communication complexity of inner product on $m$ bits is $\Omega(m)$. You can compute inner product using a protocol for the indexing function on $\{0,1\}^{2^m} \times [...
Yuval Filmus's user avatar
1 vote

Lower Bounds for the Set Disjointness Problem

This answer refers to a previous version of the question, in which the condition $a_i = b_i = 1$ was replaced by the condition $a_i = b_i$. First of all, your problem is EQUALITY in disguise (...
Yuval Filmus's user avatar
1 vote

Lower Bounds for the Set Disjointness Problem

That's simply a different problem. The set disjointness problem is defined, by common agreement, to be the problem where the universe has size $n$ and the inputs (sets) are represented as a bitvector ...
D.W.'s user avatar
  • 162k
1 vote
Accepted

Protocols for "almost equality" with one-sided error

Here is a protocol with one-sided error for the case $k=2$. Suppose we have $x,y \in \{0,1\}^n$. Sample $N$ strings $z_1,\dots,z_N$ uniformly at random from $\{1,4\}^n$. Alice sends $\alpha_j = \...
D.W.'s user avatar
  • 162k

Only top scored, non community-wiki answers of a minimum length are eligible