andy0130tw
5/9/2018 - 2:49 AM

owo unused 2.6

owo unused 2.6

First, proving Exercise 2.6: The following describes a protocol to compute a boolean function $f: X \times Y$ in $C^z(f) + 1$ bits, where $z \in \{0, 1\}$. Assume that Alice and Bob realize the way they use to cover $z$-entries and the value of $z$.
\begin{enumerate}
  \item %a
  For each rectangle, Alice tells if her $x$ is included in. This requires $C^z(f)$ bits.
  \item %b
  Bob also checks if its $y$ is included in any cover that Alice claims to contain $x$. If yes, he concludes the result is $z$, otherwise, the result is $1-z$. He tells Alice in $1$ bit.
\end{enumerate}