% ToC#361 v004a006 Jayram, Kumar, Sivakumar
% 2008-10-11
\documentclass{toc}

\usepackage{nicefrac}

\tocdetails{%
  volume=4, number=6, year=2008, firstpage=129,
    received={January 23, 2008},
    revised={September 12, 2008},
    published={October 11, 2008}
}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{prop}{Proposition}
\newtheorem*{chernoff}{Chernoff's bound}

\theoremstyle{remark}
\newtheorem*{rem*}{Remark}

\DeclareMathOperator{\sgn}{sgn}
\newcommand{\ghd}{\mathsf{GapHD}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\into}{\longrightarrow}
\newcommand{\zo}{\{0,1\}}
\newcommand{\CC}{\mathcal{C}}

\runningauthor{T. S. Jayram, Ravi Kumar, and D. Sivakumar}
\runningtitle{The One-Way Communication Complexity of Hamming Distance}
\copyrightauthor{T. S. Jayram and Ravi Kumar and D. Sivakumar}

\begin{document}

\begin{frontmatter}[classification=text]
\title{The One-Way Communication Complexity of Hamming Distance}
\tocpdftitle{The One-Way Communication Complexity of Hamming Distance}
\tocpdfauthor{T. S. Jayram, Ravi Kumar, and D. Sivakumar}

\author[jayram]{T. S. Jayram}
\author[ravi]{Ravi Kumar\thanks{Part of the work done while the author was at
the IBM Almaden Research Center.}}
\author[siva]{D. Sivakumar\footnotemark[1]}

\tockeywords{One-way communication complexity, indexing, Hamming distance}
\tocams{68Q25}
\tocacm{F.2.2}

\begin{abstract}
% SIVA
% slightly reworded to eliminate $\ghd$ from the abstract;
% the reason is that the gap, in general, could be arbitrary, and
% reserving the general name GapHD for the sqrt(n) gap might be
% presumptuous - added a line or two of text pointing this out in
% the main text
% SIVA
Consider the following version of the Hamming distance problem for
$\pm 1$ vectors
of length $n$: the promise is that the distance is either at least
$\frac{n}{2}+\sqrt{n}$ or at most $\frac{n}{2}-\sqrt{n}$, and
the goal is to find out which of these two cases occurs.
Woodruff ({\em Proc. ACM-SIAM Symposium on Discrete Algorithms, 2004\/})
gave a linear lower bound for the
randomized one-way
communication complexity of this problem.  In this note we give a simple
proof of this result. Our proof uses a simple reduction from
the indexing problem and avoids
the VC-dimension arguments used in the previous paper. As shown
by Woodruff (\emph{loc. cit.}),
%% in~\cite{Woodruff04},   %% LB 10-03
this implies an $\Omega(1/\epsilon^{2})$-space
lower bound for approximating frequency moments within a factor
$1+\epsilon$ in the data stream model.
\end{abstract}

\end{frontmatter}

\section{Introduction}

The \emph{Hamming distance} $H(x,y)$ between two vectors $x$ and $y$
is defined to be the number of positions $i$ such that $x_{i}\ne
y_{i}$.
% SIVA
% slightly reworded to call it a promise problem rather than "the Hamming
% distance problem
Let $\ghd$ denote the following promise problem:
the input consists of $\pm 1$ vectors
$x$ and $y$ of length $n$, together with the promise that either
$H(x,y)\le\frac{n}{2}-\sqrt{n}$ or $H(x,y)\ge\frac{n}{2}+\sqrt{n}$,
and the goal is to find out which of these two cases occurs. In the
\emph{one-way communication model}~\cite{KN97}, Alice gets $x$, Bob
gets $y$ and Alice sends a single message to Bob using which Bob
outputs the desired answer. We will also allow the protocols to be
randomized in which case both Alice and Bob have access to a public
random string, and the correct answer must be output with probability
at least $\nicefrac{2}{3}$. The cost of such a protocol is the
maximum number of bits communicated by Alice over all inputs. The
randomized one-way communication complexity of $\ghd$ is the cost of
the minimum-cost one-way protocol for $\ghd$.

Woodruff~\cite{Woodruff04} showed a tight $\Omega(n)$ lower bound for
$\ghd$ and used it to obtain an $\Omega(1/\epsilon^{2})$-space
lower bound for approximating frequency moments within a factor
$1+\epsilon$ in the data stream model. In this note we show a simpler
proof of the linear lower bound for $\ghd$;
our proof uses an easy reduction
from the \emph{indexing} problem and avoids the VC-dimension arguments
in~\cite{Woodruff04}. We will present two different reductions: the
first reduction uses Rademacher sums and the second reduction treats
the indexing problem from a geometric viewpoint.

Subsequent to discussing our proof with Woodruff, he obtained~\cite{wood-thesis} two
alternative proofs of the $\Omega(n)$ lower bound for $\ghd$.  The first
proof~\cite[Section 4.3]{wood-thesis} is similar in spirit to ours, and
presents a reduction from the indexing problem.  The
second proof~\cite[Section 4.4]{wood-thesis} establishes the $\Omega(n)$
lower bound for $\ghd$ under the uniform product distribution of inputs,
using combinatorial and information-theoretic arguments.
For the more general version of the
gap Hamming problem where the goal is to distinguish between $H(x, y) \leq d$
and $H(x, y) \geq d(1+\epsilon)$, an algorithm of Kushilevitz, Ostrovsky,
and Rabani~\cite{KOR} yields an $O(1/\epsilon^2)$ upper bound (independent
of $d$).
Finally,
the multi-round randomized communication complexity of $\ghd$ is still open;
we conjecture an $\Omega(n)$ lower bound.

\section{Main result}

In this note we give a simple proof of the following result.
\begin{thm}[Woodruff]
The randomized one-way communication complexity of $\ghd$
is linear in the length of the input.
\end{thm}
\begin{proof}
We begin by
recalling the indexing problem: Alice gets a set $T\subseteq[n]$, Bob
gets an element $i\in[n]$, and the goal is to compute whether $i\in T$.
We know that this has an $\Omega(n)$ lower bound in the one-way communication
model (\eg, see~\cite{KNR99} or~\cite{BJKS02} for a sharp bound in terms of the
error probability; for completeness, we include a self-contained elementary
proof of this result in \expref{Section}{sec:index}).

Let Alice's input be $T\subseteq[n]$ and Bob's input be $i\in[n]$.
Transform $T$ to a vector $u\in\{-1,+1\}^{n}$ by setting
$u_j = -1$ if $j \in T$ and $u_j = +1$ if $j \not\in T$.
Let $e_{j}$ denote the standard 0-1 basis vector corresponding
to Bob's input.

Alice and Bob will use public randomness to realize an instance
$x,y\in\{-1,+1\}^{N}$
of $\ghd$, for some $N$ to be specified later, as follows.
Pick $N$ i.i.d. vectors $r^{1},r^{2},\dots,r^{N}$ in $\mathbb{R}^{n}$
where the distribution $\mu$ of each $r^{k}$ will be specified later.
Define $x_{k}\triangleq\sgn(\langle u,r^{k}\rangle)$ and
$y_{k}\triangleq\sgn(\langle e_{i},r^{k}\rangle)$
for all $k$.
Since $r^{k} \in \{-1,+1\}^n$, we have
$\sgn(\langle e_{i}, r^{k}\rangle) = r^k_i$.
Also note that
\[
H(x,y) =
|\{ k : \sgn(\langle u,r^k\rangle)\ne\sgn(\langle e_{i},r^k\rangle)\}| =
|\{ k : \sgn(\langle u,r^k\rangle)\ne r^k_{i}\}|\,.
\]

We will show that if $r\sim\mu$,
\begin{equation}
\label{eq:gap}
\Pr[\sgn(\langle u,r\rangle)\ne r_i]
\begin{cases}
\ge \frac{1}{2}+\frac{c}{\sqrt{n}} & \text{if }u_{i}=-1,\\
\le \frac{1}{2}-\frac{c}{\sqrt{n}} & \text{if }u_{i}=+1,\end{cases}
\end{equation}
for some positive constant $c>0$.

We will use the following version of Chernoff's bound (\eg, see~\cite{mcd98}):
\begin{chernoff}
Let $X_1,X_2,\dots,X_N$ be $N$ i.i.d. 0-1 random variables and
$X = \sum_{k=1}^N X_k$. Then
\[
\Pr[X - \E[X] > \epsilon] \le e^{-2\epsilon^2/N} \quad \text{and} \quad
\Pr[X - \E[X] < -\epsilon] \le e^{-2\epsilon^2/N}\,.
\]
\end{chernoff}
Set $N=4n/c^2$ and $\epsilon=1/\sqrt{N}$.
By Chernoff's bound, with probability at least
$\nicefrac{2}{3}$, we have that either
$H(x,y) \ge \tfrac{N}{2}+\sqrt{N}$ if $u_{i}=-1$, or
$H(x,y) \le \tfrac{N}{2}-\sqrt{N}$
if $u_{i}=+1$. Therefore, given a protocol for $\ghd$,
we have a protocol for the indexing problem. Since the indexing
problem has a linear lower bound and $N=O(n)$, this
proves the linear lower bound for $\ghd$.


We now establish~\eqref{eq:gap} by giving two different proofs.

\paragraph*{\sl Rademacher sums:}

Assume that $n$ is odd.
Let $\mu$ be the uniform distribution over
the vectors in $\{-1,+1\}^{n}$ and let $r\sim\mu$. Note that
since both $u$ and $r$
are $\pm 1$ vectors and $n$ is odd, $\langle u, r \rangle \neq 0$.
Write $\langle u,r\rangle=u_{i}r_{i}+w$,
where $w\triangleq\sum_{j\ne i}u_{j}r_{j}$. Note that $w$ is independent
of $r_{i}.$ Fix a value for $w$; there are two cases to consider:
\begin{itemize}
\item If $w\ne0$, then $|w|\ge2$ since $w$ is a sum of an even number
of $\pm1$ values. Therefore, $\sgn(\langle u,r\rangle)=\sgn(w)$,
implying that
\begin{equation}
\label{eq:w-nonzero}
\Pr[\sgn(\langle u,r\rangle)
\ne r_i \mid w \ne 0]
=\Pr[\sgn(w)\ne r_{i} \mid w \ne 0]=\frac{1}{2}\,.
\end{equation}

\item If $w=0$, then $\sgn(\langle u,r\rangle)=u_{i}r_{i}$. Using
the independence of $w$ and $r_{i}$, we obtain
\begin{equation}
\label{eq:w-zero}
\begin{split}
\Pr[\sgn(\langle u,r\rangle)\ne r_i\mid w = 0]
& =\Pr[u_{i}r_{i} \ne r_{i} \mid w = 0]\\
& =\Pr[u_{i}r_{i} \ne r_{i}]\\
& =\begin{cases}
    1 & \text{if $u_{i}=-1$,}\\
    0 & \text{if $u_{i}=+1$.}\end{cases}
\end{split}
\end{equation}

\end{itemize}
Now $w$ is the sum of $n-1$ i.i.d. random variables each of which is
distributed uniformly in $\{-1,+1\}$. Since $n$ is odd, assuming
it is large enough,
$\Pr[w=0] \geq c'/\sqrt{n}$, for some constant $c'>0$ (by Stirling's formula).
Combining this with~\eqref{eq:w-nonzero}
and~\eqref{eq:w-zero}, and letting $c = c'/2$, we obtain
\eqref{eq:gap}.

\paragraph*{\sl Geometry:}

The key idea is to view $u$ and $e_{i}$ as vectors in Euclidean space
and apply the inner product protocol given in~\cite{KNR99}. This protocol
uses the technique of~\cite{GW95}, which arose in the context of
rounding the solution of a semi-definite program.
For the sake of completeness, we sketch this argument. Define $\mu$ such
that $r\sim\mu$ is a uniformly chosen $n$-dimensional unit vector.
Let $r'$ be the projection of $r$ in the plane spanned by $u$ and $e_i$.
Then by rotational symmetry, the direction of $r'$ is uniform in this plane.
If $\hat{u}$ denotes the unit vector in
the direction of $u$, then it follows\footnote{
Note that the events $\langle u, r\rangle = 0$
and $\langle e_i, r\rangle = 0$ have probability measure zero; if either
happens, Alice and Bob will abandon the protocol; this adds a negligible
quantity to the error probability.
} that
\begin{equation}
\label{eq:prob}
\Pr[\sgn(\langle u,r\rangle)
\ne r_i]
=\frac{\arccos(\langle\hat{u},e_{i}\rangle)}{\pi}
=\frac{1}{\pi}\cdot\arccos\left(\frac{u_{i}}{\sqrt{n}}\right)\,.
\end{equation}
Now, for any $z\in[-1,1]$, $\arccos(z)=\frac{\pi}{2}-\arcsin(z)$.
Since $\sin(z) \leq z$ for $z \geq 0$, we have $\arcsin(z) \geq z$ for
$0 \leq z \leq 1$.
Substituting in~\eqref{eq:prob}, we conclude
\[\Pr[\sgn(\langle u,r\rangle)
\ne\sgn(\langle e_{i},r\rangle)]
\begin{cases}
\ge \frac{1}{2}+\frac{1}{\pi \sqrt{n}} & \text{if $u_{i}=-1$,}\\
\le \frac{1}{2}-\frac{1}{\pi \sqrt{n}} & \text{if $u_{i}=+1$},
\end{cases}\]
as required.
\end{proof}

\paragraph*{Remark.}
The geometric approach shown above uses an infinite amount
of randomness which is not part of the standard model. However, the
important point is that the space of inputs and messages are finite,
therefore, the lower bounds for indexing and consequently for the
$\ghd$ will continue to hold. Alternatively, one can also
prove the above bounds using finite amount of randomness by considering
finite-precision versions of the random vectors (as was done in~\cite{KNR99};
see also~\cite{Newman}).

\section{Indexing lower bound}
\label{sec:index}

In this section, we present an elementary and self-contained proof of an
$\Omega(n)$ lower bound on the randomized one-way communication complexity
of the indexing problem. A more general result, involving
the VC-dimension and shatter coefficients, appears in~\cite{KNR99,BJKS02}.
The proof is intended to be elementary to present, and therefore,
the constants are not chosen optimally.  The proof borrows ideas from~\cite{BKS02};
the use of error-correcting codes for data stream lower bounds
also appears in~\cite{AMS}.

The indexing problem may also be thought of as a problem on strings:
Alice is given a string $x \in \zo^n$ and Bob
is given an index $i \in [n]$, and the goal is for Bob to
learn $x_i$, after receiving a single message from Alice.
Alice and Bob are both allowed to be randomized.  From the easy direction
of Yao's min-max principle, it follows that if there is a randomized
communication protocol that solves every instance of indexing with
probability of error
at most $\delta$, then for any distribution $\mu$ on the inputs for indexing,
there is a deterministic protocol that works correctly with probability
at least $1 - \delta$ when the inputs are chosen according to $\mu$.
Furthermore, if the randomized protocol is one-way, then so is the
resulting deterministic protocol.
The rest of this section presents an ensemble of
distributions $\mu = \mu(\delta) = \{\mu_n\}$
(for suitably large $\delta > 0$)
such that for some absolute constant $\epsilon > 0$ and
for sufficiently large $n$, in any deterministic
communication protocol that works correctly on all but $\delta$ fraction of
inputs from $\mu_n$, Alice must communicate at least $\epsilon n$ bits to
Bob.

An $(n, d)$-error correcting code
is a collection $\CC$ of strings in $\zo^n$
such that for any distinct pair of strings
$x, y \in \CC$, $H(x,y) \ge d$, where $H$ denotes the Hamming distance.
It is well-known%
\footnote{
For example, Justesen codes (see~\cite{vanLint})
are a simple and explicit construction.
It can be shown via the probabilistic method, using Chernoff
bounds, that there exists $\alpha$ such that for any $\Delta < 1/2$
and sufficiently large $n$, there is an $(n, \Delta n)$-error correcting
code of size $2^{\alpha n}$.  For our proof, the explicitness of the code
is not necessary.
}
that there are constants $\alpha > 0, \Delta > 0$ such that
for all sufficiently large $n$,
there is an $(n, \Delta n)$-error correcting code
$\CC_n$ of size $2^{\alpha n}$.
The distribution $\mu_n$
we will use will pick a string $x$ for Alice uniformly
from the collection $\CC_n$, and an index $i \in [n]$ for Bob uniformly
at random.
Let $0 < \delta \leq \Delta/4$.

Let $\Pi$ denote a deterministic one-way
communication protocol that succeeds with probability at least $1-\delta$ when
the inputs are drawn according to $\mu_n$, and in which the number of bits
sent by Alice is at most $c$.  Since $\Pi$ is a one-way
protocol, there is a pair of functions $A: \zo^n \into \zo^c$
and $B: \zo^c \times [n] \into \zo$ that describe the
actions of Alice and Bob in the protocol $\Pi$.
First note that if $x \not= y$, since $H(x, y) \ge 4\delta n$,
under the uniform distribution of $i \in [n]$, we have
$x_i \not= y_i$ with probability at least $4\delta$.
Now suppose $x, y \in \CC_n$, $x \not= y$, and $A(x) = A(y) = z$.
Then, for at least $4\delta n$ distinct values of $i$,
$B(z, i)$ agrees with precisely one of $x_i$ and $y_i$;
equivalently, for at least $2\delta n$ distinct values of $i$,
either $B(z, i) \neq x_i$ or $B(z, i) \neq y_i$.
Since $\Pi(x, i) = B(z, i) = \Pi(y, i)$, we have
$\Pr_i[\Pi(x,i) \not= x_i] \ge 2\delta$ or $\Pr_i[\Pi(y,i) \not= y_i]
\ge 2\delta$.
Since this is true for any pair of strings in $\CC_n$ that agree under
the map $A(\cdot)$, it follows that for any $z \in \zo^c$, for all but
one $x$ satisfying $A(x) = z$, we have $\Pr_i[\Pi(x,i) \not= x_i] \ge 2\delta$.
If the total error of the protocol under the distribution $\mu_n$ is
no more than $\delta$, we have:
$$
\frac{2^{\alpha n} - 2^c}{2^{\alpha n}} 2\delta < \delta\,,
$$
whence it follows that $c > \alpha n - 1$.

\subsection*{Acknowledgments}

We thank Laci Babai and the anonymous reviewers for many useful
comments.

\bibliographystyle{tocplain}
\bibliography{v004a006}


\begin{tocauthors}
\begin{tocinfo}[jayram]
  T. S. Jayram \tocabout\\
  IBM Almaden Research Center \\
    650 Harry Rd \\
    San Jose, CA 95120\\
  jayram\tocat{}almaden\tocdot{}ibm\tocdot{}com \\
  \url{http://www.almaden.ibm.com/cs/people/jayram} \\
\end{tocinfo}
\begin{tocinfo}[ravi]
  Ravi Kumar \tocabout\\
    Yahoo! Research \\
  701 First Ave \\
    Sunnyvale, CA 94089\\
  ravikumar\tocat{}yahoo-inc\tocdot{}com  \\
  \url{http://research.yahoo.com/Ravi_Kumar} \\
\end{tocinfo}
\begin{tocinfo}[siva]
  D. Sivakumar \tocabout\\
  Google Inc. \\
    1600 Amphitheatre Parkway \\
    Mountain View, CA 94043\\
    siva\tocat{}google\tocdot{}com \\
    \url{http://globofthoughts.blogspot.com} \\
\end{tocinfo}
\end{tocauthors}

\begin{tocaboutauthors}
\begin{tocabout}[jayram]
{\sc T. S. Jayram} (aka {\sc Jayram Thathachar}) has been at \href{http://www.almaden.ibm.com/}{IBM 
Research} since 1998.  He obtained his Bachelors degree in Computer Science 
from \href{http://www.iitm.ac.in/}{IIT Madras}, Chennai and his Masters and \phd\ in Computer Science and 
Engineering from the \href{http://www.washington.edu/}{University of Washington}, Seattle, under the 
supervision of \href{http://www.cs.washington.edu/homes/beame/}{Paul Beame}.  He now manages the Algorithms and 
Computation group at IBM Almaden.  His primary research interests are 
in massive data sets and computational complexity.
\end{tocabout}
\begin{tocabout}[ravi]
{\sc Ravi Kumar} has been at \href{http://research.yahoo.com/}{Yahoo! Research} since July 2005.  Prior 
to this, he was a research staff member at the \href{http://www.almaden.ibm.com/}{IBM Almaden Research Center} 
in the Computer Science Principles and Methodologies group.  He obtained 
his \phd\ in Computer Science from \href{http://www.cornell.edu/}{Cornell University} under \href{http://people.csail.mit.edu/ronitt}{Ronitt Rubinfeld} in December 1997. 
His primary interests are web algorithms, algorithms for large data sets, 
and theory of computation.
\end{tocabout}
\begin{tocabout}[siva]
{\sc D. Sivakumar} ({\sc Siva}) is interested in theoretical computer 
science, organizing the world's information, and everything in between.  He 
has been at \href{http://research.google.com/}{Google Research} since 2005, before which he was on the Research 
Staff at the \href{http://www.almaden.ibm.com/}{IBM Almaden Research Center}, San Jose, CA.  Before finding his 
home in the pleasant environs of northern California, he spent a few years 
in the steam chamber of Houston, TX, as a member of the faculty of 
Computer Science at the \href{http://www.uh.edu/}{University of Houston}, and a few years in the 
freezer that is Buffalo, NY, where he received his \phd\ in Computer 
Science from the \href{http://www.buffalo.edu/}{State University of New York}
under the wise tutelage of 
\href{http://www.cse.buffalo.edu/~regan}{Ken Regan}, 
\href{http://pages.cs.wisc.edu/~jyc}{Jin-Yi Cai}, and 
\href{http://www.cse.buffalo.edu/~selman}{Alan Selman}.
\end{tocabout}
\end{tocaboutauthors}

\end{document}
