6

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 \supseteq C \cap I$. The players stop once $|V_m| \leq 1$. At this point they can answer the question using $O(1)$ communication. At round $i$, the players know $V_{...


5

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$ denote the matrix corresponding to this problem: $M_f(x,y) = 1$ if the answer is Yes, and $M_f(x,y) = -1$ if the answer is No. The discrepancy method shows ...


4

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 + z_1z_4z_5 + z_2z_3z_4 + z_2z_3z_5 + \\ z_1z_2z_6 + z_1z_3z_6 + z_2z_4z_6 + z_3z_5z_6 + z_4z_5z_6. $$


4

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 fewer than $|V_{i-1}|/2$ neighbors in $V_{i-1}$. $V_i$ is set to be this neighborhood (along with v). Observe that $|V_i|< |V_{i-1}|/2+1$. We will be a little ...


3

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 willing to accept a randomized protocol. Let $H(\cdot)$ denote a randomized hash function. Do binary search on $i$ to find the smallest $i$ such that $H(a_1,\...


3

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$ indices, then the probability of finding the index in which they differ is $\frac{k}{n}$, so if you want this to be constant you must have $k=\Omega(n)$. The ...


3

Assume that each player gets a number in $[n]$, and they can compute $h_n(x,y)$. Each player knows $n$, so if $h_n$ is computable with less than $log(n)$ communication, they can compute $h_n(n-x,y)$ in under $log(n)$ bits of communication. Since you have $h_n(n-x,y)=1 \iff x=y$ then you managed to compute $\delta_{x,y}$ in sub logarithmic communication, ...


3

Geometric rectangle is not a standard term. That's why they define it in the question. In communication complexity, Alice has an input from the set $X$, and Bob has an input from the set $Y$. Usually we assume that the sets $X,Y$ are unstructured. A combinatorial rectangle is a subset of $X \times Y$ of the form $A \times B$, where $A \subseteq X$ and $B \...


3

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 not regular, but it has communication complexity $O(1)$.


3

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 other one, who can then compute the output locally (although note that there are some very nice and non-trivial probabilistic algorithms -- e.g. for EQ -- even ...


3

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 district, the problem is known as Element distinctness problem. And, this problem has an $\Omega(n \log n)$ lower bound complexity. More technically, your problem can ...


2

Deterministic communication complexity depends only on the support of the input distribution (the "promise"). Even if $H(X|Y),H(Y|X) < 1$ the distribution $(X,Y)$ could have full support, so the $\Omega(n)$ bound still holds.


2

The protocol gives you a covering of the zeroes using $2n$ rectangles $R_{i,b} = X_{i,b} \times Y_{i,1-b}$, where $X_{i,b}$ (or $Y_{i,b}$) is the set of words whose $i$th bit equals $b$.


2

Your definition is wrong. The correct definition is as follows. A protocol $P$ is $\epsilon$-differentially private (for $\epsilon > 0$) if for any two inputs $Z_1,Z_2$ differing in a single coordinates and any $p$, $$ e^{-\epsilon} \leq \frac{\Pr[P(Z_1) = p]}{\Pr[P(Z_2) = p]} \leq e^\epsilon. $$ For small $\epsilon>0$, $e^\epsilon \approx 1 + \epsilon$...


2

The view of Alice is what Alice gets to see; it is a probability distribution that depends on the inputs of both players $x,y$. It is a distribution over triples $(x,\tau,r_A)$, where $x$ is Alice's input, $\tau$ is the transcript of the protocol, and $r_A$ is Alice's private randomness. This probability distribution depends both on $x$ and on Bob's input $y$...


2

Your conjecture is refuted by the language $\{ 0^n : \text{$n$ is not a power of $2$}\}$. Let $\{(x_i,y_i) : i \in \mathbb{N}\}$ be an infinite fooling set for this language. We can identify $x_i,y_i$ with integers. These pairs have to satisfy the following conditions: $x_i + y_i$ is not a power of $2$. For each $i \neq j$, either $x_i + y_j$ is a power of $...


2

The notion of round should be quite similar to the intuitive idea of "one step of the protocol". At any round you are allowed to send 1 message (of any size) and/or receive one message. The message you send at round $i$ may depend on all the information you have up to round $i$, but it cannot depend on the message you receive at round $i$ (or later). It ...


2

Hint: The condition $x + y + xy = 0$ is equivalent to the condition $1 + x + y + xy = 1$, i.e. $(1 + x)(1 + y) = 1$, or in other words, $$ (1+x)^{-1} = 1+y. $$


2

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 players with unlimited computational power, each of whom holds an $n$ bit input, say $x$ and $y$. Neither knows the other’s input, and they wish to collaboratively ...


2

One possibly better approach would be to use a Merkle tree, or some other hierarchical data structure like that. If there's a large set of transactions that the sender can identify as probably already known to the recipient, then this might save a significant amount of data transfer. Build a binary tree, where each leaf corresponds to a single transaction, ...


2

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.): The two parties decide on a random string $z \in \mathbb{Z}_{2k+3}^n$, compute $\alpha = \langle x,z \rangle$ and $\beta = \langle y,z \rangle$, and accept if ...


2

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)$ for inner product? We want each of $X,Y$ separately to be quite random, and we want $X\cdot Y$ to be mostly zero, say $X \cdot Y$ contains at most a single $1$....


2

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 requires $\Omega(n)$ communication. When $\epsilon = 1$, the problem becomes easy (send the first bit).


1

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 the form $A\times B$, where $A\subseteq \{0,1\}^n$ and $B\subseteq \{0,1\}^n$. For all $x\in \{0,1\}^n$, we can think of $x$ as the characteristic vector of a ...


1

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,\ell_n,u_1,\dots,u_n$.


1

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 value of $X,Y$. Now unconditionally, $X,Y$ are dependent (there is probability $1/2$ that they are Heads,Heads and probability $1/2$ that they are Tails,Tails). ...


1

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 each message $x$, the probability that Bob is correct is at least $1-\epsilon$. Let $X$ be a random $n$-bit string, and let $\Pi$ be the corresponding transcript. ...


1

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 [2^m]$ as follows: denoting Alice's input by $x \in \{0,1\}^m$ and Bob's by $y \in \{0,1\}^m$, Alice computes a new vector $X$ by $X_y = \mathsf{IP}(x,y)$, and ...


1

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 (complement one of the vectors to see why). The complexity of EQUALITY is still $\Theta(n)$ in the deterministic case, but it drops down to $\Theta(\log n)$ in the ...


1

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 of length $n$. In other words, when you hear the phrase "set disjointness problem", you can know that's what they're referring to, and not the problem you ...


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