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 \...


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$....


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 ...


1

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 = \sum_i x_i z_{j,i} \bmod 5$ to Bob, and Bob sends $\beta_j = \sum_i y_i z_{j,i} \bmod 5$ to Alice. Both parties compute $\gamma_j = \alpha_j - \beta_j \bmod 5$. ...


1

The author describes an algorithm due to Ahlswede and Cai to solve the set intersection problem, and then describes his generalization to the number-in-hand setting with any number of players. I will only describe the two player setting. Ahlswede and Cai consider an algorithm of the following form. Alice gets a set $X \subseteq \{1,\ldots,n\}$, and Bob gets ...


1

Round: The protocol (or the communication game) proceeds in rounds. In each round, some bits are communicated. In the simple model of Alice and Bob to evaluate some function f, it depends on the protocol P that specifies which player sends a bit of communication (and of course, what bit to send) next. Complexity measure: The communication complexity refers ...


1

There is a cheap lower bound of $\Omega(r)$ obtained by reduction. Suppose for simplicity that the $r$ dIstinguished coordinates are the first $r$. Let $g(x_1,\ldots,x_r) = f(x_1,\ldots,x_r,0,\ldots,0)$. Your condition on $f$ implies that $g$ satisfies Jukna's condition on $g$, so $g$ has communication complexity $\Omega(r)$. Any protocol for $f$ also works ...


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