Tag Info

Accepted

• 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 ...
• 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 ...
• 278k
1 vote
Accepted

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 [... • 278k 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 (... • 278k 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 ... • 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 = \...
• 162k

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