\documentclass{article}
\input{6897-preamble}

\begin{document}
\psetnum{6}
\date{2005/03/14}
\begin{pset}

\def\GT{\mathsf{GT}}
  
\paragraph{Upper bound}
We give a protocol that uses $t$ rounds and message length $m =
\bigO{n^{\nicefrac1t} \lg n}$ to decide $\GT(x,y)$. Assume that
beforehand Alice and Bob decide on a random hash function via public
coin flips. Then our procedure is as follows: Alice divides the
$n$-bit integer $x$ into $k$ chunks of $\nicefrac nk$ bits, then
hashes each chunk to a value of size $n^\zeta$ (for some constant
$\zeta$ to be specified later), and transmits the hashes to Bob. This
message has length $k \lg \left(n^\zeta\right) = \bigO{k \lg n}$ bits.
When Bob receives the hashes, he similarly divides his integer $y$
into $k$ chunks, and compares the hashes to find the highest-order
chunk that differs (call it $x'$ and $y'$). Bob then recurses on this
$y'$, dividing it into $k$ chunks (now of size $\nicefrac n{k^2}$
bits), hashing each chunk, and transmitting them to Alice (along with
a small constant amount of information to indicate which of her chunks
he is recursing on). Alice and Bob repeat this protocol, reducing the
size of their integers by a factor of $k$ each round, until the
integers have been reduced to $k$ bits, at which time the player whose
turn it is can simply transmit his or her full remaining integer to
the other player, who can compute the $\GT$ result directly by
comparing the transmitted integer and his or her own integer.

We now analyze this algorithm. Note that after each round the size of
the problem is reduced by a factor of $k$, so to complete the
algorithm in $t$ rounds, we require $t = \bigTheta{\log_k n}$, or $k =
\bigTheta{n^{\nicefrac1t}}$. Then the message length is
$\bigO{n^{\nicefrac1t} \lg n}$, which is the desired bound. Note
however that there is a probability of error due to hash collisions,
which we will show is small. We are hashing at most $n$ bits to $\lg n^\zeta$ bits, so the probability that two different values hash to the
same value is bounded by $\nicefrac1{n^\zeta}$. An error only occurs if the
highest-order differing chunks hash to the same value, so the
probability of identifying the correct chunk $x'$ is $1 -
\nicefrac1{n^\zeta}$. So the probability that no bad collisions occur
at any round is $\left(1 - \nicefrac1{n^\zeta}\right)^t \approx e^{-
  \nicefrac{t}{n^\zeta}}$. If we choose $\zeta$ sufficiently large, we
can make this probability above $\nicefrac23$, guaranteeing that the
algorithm gives the correct result with probability $\nicefrac23$.

\paragraph{Lower bound}
We show by contradiction that no protocol exists unless $m =
\bigOmega{\frac{n^{\nicefrac1t}}{t^2}}$. Suppose such a protocol
exists. Then the $k$-fold of $\GT$, $\GT^{(k)}$, in which Alice knows
$\tup<x_1,\ldots,x_k>$ and Bob knows $\tup<y, i, x_1,\ldots,x_i>$ and
we wish to compute $\GT(x_i,y)$, can be also be solved using $t$
rounds and $m$ messages. We can solve $\GT^{(k)}(x_i, y)$ using $\GT$
by concatenating the bitstrings and computing $\GT(x_1 x_2 \cdots
x_k,\;\; x_1 x_2 \cdots x_i
\mathtt{(1)}^{\left(\frac{k-i}{k}\right)n})$. This is true exactly
when $\GT^{(k)}(x_i, y)$.

Suppose our protocol for $\GT$ has error probability no more than
$\nicefrac13$. We repeatedly reduce it to $\GT^{(k)}$ as described
above, then apply the round elimination lemma, which reduces the
number of rounds by 1 while adding $\bigO{\sqrt{\frac{m}{k}}}$ error
probability. Thus, eliminating $t$ rounds gives a zero-round protocol
with error probability $\nicefrac13 + t\bigO{\sqrt{\frac{m}{k}}}$. We
want this to be strictly greater than $\nicefrac12$, so
$\bigO{\sqrt{\frac{m}{k}}} < \frac{1}{6t}$ and hence $k =
\bigOmega{mt^2}$. So $m = \bigOmega{\frac{k}{t^2}}$. We restrict
ourselves to values of $n \ge k^t$: since the problem size is divided
by $k$ on each of the $t$ rounds, if this condition does not hold then
the zero-round protocol is for less than one bit, which is
meaningless. Then $n^{\nicefrac1t} \ge k$. Applying this to the bound
on $m$, $m = \bigOmega{\frac{n^{\nicefrac1t}}{t^2}}$, which is the
desired bound. In these cases, we have used the protocol that we
assumed the existence of to give a zero-round protocol that computes
$\GT$ on a value of at least one bit with probability strictly greater
than the $\nicefrac12$ of random guessing, which is a
contradiction. So the assumed protocol cannot exist. This proves the
lower bound.
\end{pset}
\end{document}