\xbar
Dept.\ of Combinatorics and Optimization and Instuitute for Quantum Computing
Waterloo
ON
{Univ. of Waterloo}
College Park
{Univ. of MD at College Park}
Dept.\ of Computer Science
Alice and Bob want to know if two strings of length $n$ are almost equal. That is, do they differ on at most $a$ bits? Let $0\le a\le n-1$. We show that any deterministic protocol, as well as any error-free quantum protocol ($C^*$ version), for this problem requires at least $n-2$ bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly $a$ bits. We also prove a lower bound of $n/2-1$ for error-free $Q^*$ quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.
cs0411076.tex
\documentclass[11pt]{article}
\usepackage{fullpage}
\begin{document}

% This is a file of macros and definitions that may come up in
% ANY LATEX paper.  Typically I'll use this file and some other file in the
% directory of the paper, this one for general math things, that one for
% things specific to that paper.
%
% font's used and general paper things.
\font\tenrm=cmr10
\font\ninerm=cmr9
\font\eightrm=cmr8
\font\sevenrm=cmr7
% \font\title=cmbx10 scaled \magstep1 % extra big title font
\font\ss=cmss10 % used by \proof
\font\smallcaps=cmcsc10 % used to label Theorems, etc.
% imhibit black bars on overflows
%
\overfullrule=0pt
%
% today's date
%
%
% English words that I always italizice in papers.
% Some words that appear in math mode alot that I wasn roman
%

\newcommand{\xbar}{\overline{x}}
\newcommand{\Basethree}{\rm Base3}
\newcommand{\Basefive}{\rm Base5}
\newcommand{\KD}{\rm KD}
\newcommand{\K}{\floor{\log_{2d+1} n} }
\newcommand{\hconst}{\frac{1}{3}\cdot{\sqrt{\frac{5}{3}}}\cdot}
\newcommand{\hconstnp}{\frac{1}{3}\cdot{\sqrt{\frac{5}{3}}}}
\newcommand{\fhconst}{\frac{2}{3}\cdot{\sqrt{\frac{5}{3}}}\cdot}
\newcommand{\fhconstnp}{\frac{2}{3}\cdot{\sqrt{\frac{5}{3}}}}
\newcommand{\const}{\frac{1}{12}\cdot{\sqrt{\frac{5}{3}}}\cdot}
\newcommand{\constnop}{\frac{1}{12}\cdot{\sqrt{\frac{5}{3}}}}
\newcommand{\var}{\frac{1}{5}}
\newcommand{\zeq}{\sqrt{\frac{3}{5}}}
\newcommand{\constnum}{0.11}

\newcommand{\exf}{\frac{19}{90}}
\newcommand{\almost}{\frac{1}{10}}

\newcommand{\hconstinf}{\frac{\sqrt {15}}{12}}
\newcommand{\constinf}{\frac{\sqrt {15}}{6}}
\newcommand{\varinf}{\frac{4}{45}}
\newcommand{\zeqinf}{\sqrt{\frac{4}{15}}}
\newcommand{\constinfnum}{1.58}

\newcommand{\lam}{\lambda}
\newcommand{\Abar}{\overline{A}}
\newcommand{\Tbar}{\overline{T}}
\newcommand{\sm}{{\rm small}}
\newcommand{\bi}{{\rm big}}
\newcommand{\ts}{t^{\sm}}
\newcommand{\tb}{t^{\bi}}
\newcommand{\tsj}{t^{\sm,j}}
\newcommand{\tbj}{t^{\bi,j}}
\newcommand{\Bs}{B^{\sm}}
\newcommand{\Bb}{B^{\bi}}
\newcommand{\Ld}{L_{\rm diag}}
\newcommand{\st}{\, : \, }
\newcommand{\kstar}{{\textstyle *}}
\newcommand{\bits}[1]{\{0,1\}^{{#1}}}
\newcommand{\bit}{\{0,1\}}
\newcommand{\nat}{{\sf N}}
\newcommand{\implies}{\Rightarrow}
\newcommand{\into}{\rightarrow}
\renewcommand{\AE}{\forall^\infty}
\newcommand{\IO}{\exists^\infty}
%\newcommand{\IO}{\buildrel \infty \over \exists\!\!}
\newcommand{\ep}{\epsilon}
\newcommand{\es}{\emptyset}
\newcommand{\isom}{\simeq}
\newcommand{\nisom}{\not\simeq}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\nth}{n^{th}}
%
% definitions with macros
%
\newcommand{\inter}{\cap}
\newcommand{\union}{\cup}
\newcommand{\sig}[1]{\sigma_{#1} }
\newcommand{\s}[1]{\s_{#1}}
\newcommand{\dash}{\hbox{-}}
\newcommand{\infinity}{\infty}
\newcommand{\ie}{\hbox{ i.e.  }}
\newcommand{\eg}{\hbox{ e.g.  }}

% BEIGEL"S MACROS FOR THEOREM STUFF.
% WHEN DOING A THEOREM DO
% \begin{theorem}\label{th:NAME}
%
% WHEN DOING A LEMMA DO
%
% \begin{lemma}\label{le:NAME}
%
%
%  also works for section se, corollary co, definition de,
%  fact fa
%
%  use \ref, like
%  I will prove theorem ~\ref{th:ONE}
%
\newcounter{savenumi}
\newenvironment{savenumerate}{\begin{enumerate}
\setcounter{enumi}{\value{savenumi}}}{\end{enumerate}
\setcounter{savenumi}{\value{enumi}}}
\newtheorem{theoremfoo}{Theorem}[section] %by chapter in report style
\newenvironment{theorem}{\pagebreak[1]\begin{theoremfoo}}{\end{theoremfoo}}
\newenvironment{repeatedtheorem}[1]{\vskip 6pt
\noindent
{\bf Theorem #1}\ \em
}{}

\newtheorem{lemmafoo}[theoremfoo]{Lemma}
\newenvironment{lemma}{\pagebreak[1]\begin{lemmafoo}}{\end{lemmafoo}}
\newtheorem{conjecturefoo}[theoremfoo]{Conjecture}
\newtheorem{research}[theoremfoo]{Line of Research}
\newenvironment{conjecture}{\pagebreak[1]\begin{conjecturefoo}}{\end{conjecturefoo}}

\newtheorem{conventionfoo}[theoremfoo]{Convention}
\newenvironment{convention}{\pagebreak[1]\begin{conventionfoo}\rm}{\end{conventionfoo}}

\newtheorem{porismfoo}[theoremfoo]{Porism}
\newenvironment{porism}{\pagebreak[1]\begin{porismfoo}\rm}{\end{porismfoo}}


\newtheorem{corollaryfoo}[theoremfoo]{Corollary}
\newenvironment{corollary}{\pagebreak[1]\begin{corollaryfoo}}{\end{corollaryfoo}}


\newtheorem{claimfoo}[theoremfoo]{Claim}
\newenvironment{claim}{\pagebreak[1]\begin{claimfoo}}{\end{claimfoo}}




%\newtheorem{exercisefoo}[theoremfoo]{Exercise}
%\newenvironment{exercise}{\pagebreak[1]\begin{exercisefoo}\rm}{\end{exercisefoo}}


\newtheorem{openfoo}[theoremfoo]{Open Problem}
\newenvironment{open}{\pagebreak[1]\begin{openfoo}\rm}{\end{openfoo}}


\newtheorem{exercisefoo}{Exercise}
\newenvironment{exercise}{\pagebreak[1]\begin{exercisefoo}\rm}{\end{exercisefoo}}

\newcommand{\fig}[1] %usage:\fig{file}
{
 \begin{figure}
 \begin{center}
 \input{#1}
 \end{center}
 \end{figure}
}

\newtheorem{potanafoo}[theoremfoo]{Potential Analogue}
\newenvironment{potana}{\pagebreak[1]\begin{potanafoo}\rm}{\end{potanafoo}}

\newtheorem{notefoo}[theoremfoo]{Note}
\newenvironment{note}{\pagebreak[1]\begin{notefoo}\rm}{\end{notefoo}}

\newtheorem{notabenefoo}[theoremfoo]{Nota Bene}
\newenvironment{notabene}{\pagebreak[1]\begin{notabenefoo}\rm}{\end{notabenefoo}}

\newtheorem{nttn}[theoremfoo]{Notation}
\newenvironment{notation}{\pagebreak[1]\begin{nttn}\rm}{\end{nttn}}

\newtheorem{empttn}[theoremfoo]{Empirical Note}
\newenvironment{emp}{\pagebreak[1]\begin{empttn}\rm}{\end{empttn}}

\newtheorem{examfoo}[theoremfoo]{Example}
\newenvironment{example}{\pagebreak[1]\begin{examfoo}\rm}{\end{examfoo}}

\newtheorem{dfntn}[theoremfoo]{Definition}
\newenvironment{definition}{\pagebreak[1]\begin{dfntn}\rm}{\end{dfntn}}

\newtheorem{propositionfoo}[theoremfoo]{Proposition}
\newenvironment{proposition}{\pagebreak[1]\begin{propositionfoo}}{\end{propositionfoo}}
\newenvironment{prop}{\pagebreak[1]\begin{propositionfoo}}{\end{propositionfoo}}

\newenvironment{proof}
    {\pagebreak[1]{\narrower\noindent {\bf Proof:\quad\nopagebreak}}}{\QED}
\newenvironment{sketch}
    {\pagebreak[1]{\narrower\noindent {\bf Proof sketch:\quad\nopagebreak}}}{\QED}
\newenvironment{comment}{\penalty -50 $(*$\nolinebreak\ }{\nolinebreak $*)$\linebreak[1]\ }

%\renewcommand{\labelenumi}{\roman{enumi}.}



\newenvironment{algorithm}[1]{\bigskip\noindent ALGORITHM~#1\renewcommand{\theenumii}{\arabic{enumii}}\renewcommand{\labelenumii}{Step \theenumii :}\begin{enumerate}}{\end{enumerate}END OF ALGORITHM\bigskip}

\newenvironment{protocol}[1]{\bigskip\noindent PROTOCOL~#1\renewcommand{\theenumii}{\arabic{enumii}}\renewcommand{\labelenumii}{Step \theenumii :}\begin{enumerate}}{\end{enumerate}END OF PROTOCOL\bigskip}

\newenvironment{red}[1]{\noindent REDUCTION~#1\renewcommand{\theenumii}{\arabic{enumii}}\renewcommand{\labelenumii}{Step \theenumii :}\begin{enumerate}}{\end{enumerate}END OF REDUCTION}



\newenvironment{con}{\noindent CONSTRUCTION\renewcommand{\theenumii}{\arabic{enumii}}\renewcommand{\labelenumii}{Step \theenumii :}\begin{enumerate}}{\end{enumerate}END OF CONSTRUCTION}



\newenvironment{alg}[1]{\bigskip\noindent ALGORITHM~#1\renewcommand{\theenumii}{\arabic{enumii}}\renewcommand{\labelenumii}{Step \theenumii :}\begin{enumerate}}{\end{enumerate}END OF ALGORITHM\bigskip}



\newcommand{\yyskip}{\penalty-50\vskip 5pt plus 3pt minus 2pt}
\newcommand{\blackslug}{\hbox{\hskip 1pt
        \vrule width 4pt height 8pt depth 1.5pt\hskip 1pt}}
\newcommand{\QED}{{\penalty10000\parindent 0pt\penalty10000
        \hskip 8 pt\nolinebreak\blackslug\hfill\lower 8.5pt\null}
        \par\yyskip\pagebreak[1]}

\newcommand{\BBB}{{\penalty10000\parindent 0pt\penalty10000
        \hskip 8 pt\nolinebreak\hbox{\ }\hfill\lower 8.5pt\null}
        \par\yyskip\pagebreak[1]}

\newcommand{\PYI}{CCR-8958528}
\newtheorem{factfoo}[theoremfoo]{Fact}
\newenvironment{fact}{\pagebreak[1]\begin{factfoo}}{\end{factfoo}}
\newenvironment{acknowledgments}{\par\vskip 6pt\footnotesize Acknowledgments.}{\par}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%
%%%%%%%%%%  Jim's construction macros.
%%%%%%%%%%


%%% The follow are macros for displaying block structured programs and
%%% constructions.  Basically, they are dressed up lists, like the
%%% enumerate and itemize environments.  Use  the construction environment
%%% for the outermost ``list'' of instruction and for ``sublists'' of
%%% instructions use the block environment.  E.g.,
%%%
%%% \begin{construction}
%%%   \item {\bf Program for} $M_{p,a}$.
%%%   \begin{block}
%%%     \item Input $x$.
%%%     \item Instructions.  Instructions.  Instructions.  Instructions.
%%% 	      Instructions.  Instructions.  Instructions.  Instructions.
%%%     \begin{block}
%%%        \item More instructions.  More instructions.  More
%%% 		instructions.   More instructions.
%%%        \item More instructions.  More instructions.  More
%%% 		instructions.   More instructions.
%%%     \end{block}
%%%     \item Instructions.  Instructions.  Instructions.  Instructions.
%%%     \item Instructions.  Instructions.  Instructions.  Instructions.
%%%   \end{block}
%%%   \item {\bf End program for} $M_{p,a}$.
%%% \end{construction}


\newenvironment{construction}{\bigbreak\begin{block}}{\end{block}
    \bigbreak}

\newenvironment{block}{\begin{list}{\hbox{}}{\leftmargin 1em
    \itemindent -1em \topsep 0pt \itemsep 0pt \partopsep 0pt}}{\end{list}}


%%% If you want to label the statements/blocks in your construction,  use
%%% the lblock environment instead of the block environment and for each
%%% item macro, use \item[YOUR_LABEL].  Note that labels are
%%% do-it-yourself.
%%%
%%% Note that in the following, the basic indentation of an lblock at
%%% level i of nesting (i>0) is (\dimen15 + i * \dimen16).  The default
%%% value of both \dimen15 and \dimen16 is  0.75em.

\dimen15=0.75em
\dimen16=0.75em

\newcommand{\lblocklabel}[1]{\rlap{#1}\hss}

\newenvironment{lblock}{\begin{list}{}{\advance\dimen15 by \dimen16
    \leftmargin \dimen15
    \itemindent -1em
    \topsep 0pt
    \labelwidth 0pt
    \labelsep \leftmargin
    \itemsep 0pt
    \let\makelabel\lblocklabel
    \partopsep 0pt}}{\end{list}}


%%% The lconstruction is an alternative to the construction environment
%%% which lets you temporarily change the values of \dimen15 and \dimen16.

\newenvironment{lconstruction}[2]{\dimen15=#1 \dimen16=#2
  \bigbreak\begin{block}}{\end{block}\bigbreak}


\newcommand{\Comment}[1]{{\sl ($\ast$\  #1\ $\ast$)}}


%%%%%%%%%%
%%%%%%%%%% End of Jim's construction macros.
%%%%%%%%%%

\newcommand{\Kobler}{K\"obler}
\newcommand{\Schoning}{Sch\"oning}
\newcommand{\Toran}{Tor\'an}
\newcommand{\Balcazar}{Balc{\'a}zar}
\newcommand{\Diaz}{D\'{\i}az}
\newcommand{\Gabarro}{Gabarr{\'o}}
\newcommand{\Laszlo}{L{\'a}szl{\'o}}
\newcommand{\HAM}{{\rm HAM}}
\newcommand{\eig}{eig}
%\newcommand{\SUM}{SUM}
\newcommand{\SUM}{\ \ \sum_{k=\max\{ 0,j+m-n \} }^{\min\{j,m\}}\ \ }
\newcommand{\SUMa}{\ \ \sum_{k=\max\{ 0,a+m-n \} }^{\min\{a,m\}}\ \ }
\newcommand{\HAMa}{HAM_n^{(a)}}
\newcommand{\HAMea}{HAM_n^{(=a)}}
\newcommand{\HAMeap}{HAM_n^{(=a')}}
\newcommand{\HAMeapp}{HAM_n^{(=n - a')}}


\title{Lower bounds on the Deterministic and Quantum Communication 
Complexity of $\HAMa$}

\author{
{Andris Ambainis}
\thanks{ University of Waterloo,
Dept.\ of Combinatorics and Optimization and
Instuitute for Quantum Computing,
University of Waterloo,
200 University Avenue West,
Waterloo, ON, Canada N2L 3G1
\texttt{ambainis@uwaterloo.ca}, 
Partially supported by IQC University Professorship
and CIAR.
}
\\ {\small Univ. of Waterloo}
\and
{William Gasarch}
\thanks{ University of Maryland,
Dept.\ of Computer Science and Institute for Advanced Computer Studies,
	College Park, MD\ \ 20742.
\texttt{gasarch@cs.umd.edu}, Partially supported by NSF grant CCR-01-05413.
}
\\ {\small Univ. of MD at College Park}
\and
{Aravind Srinivasan}
\thanks{ University of Maryland,
Dept.\ of Computer Science and Institute for Advanced Computer Studies,
	College Park, MD\ \ 20742.
\texttt{srin@cs.umd.edu}, Partially supported by NSF grant CCR-020-8005.
}
\\ {\small Univ. of MD at College Park}
\and
{Andrey Utis}
\thanks{ University of Maryland,
Dept.\ of Computer Science, College Park, MD\ \ 20742.
\texttt{utis@cs.umd.edu}
}
\\ {\small Univ. of MD at College Park}
}


\date{}

\maketitle

\begin{abstract}
Alice and Bob want to know if two strings of length $n$ are
almost equal. That is, do they differ on \textit{at most} $a$ bits?
Let $0\le a\le n-1$.
We show that any deterministic protocol, as well as any
error-free quantum protocol ($C^*$ version), for this problem
requires at least $n-2$ bits of communication. 
We show the same bounds for the problem of determining
if two strings differ in \textit{exactly} $a$ bits.
We also prove a lower bound of $n/2-1$ for error-free $Q^*$ quantum protocols.
Our results are obtained by lower-bounding the ranks of the
appropriate matrices. 
\end{abstract}

\section{Introduction}

Given $x,y\in \bits n$ one way to measure how much they
differ is the Hamming distance.

\begin{definition}
If $x,y\in \bits n$ then
$\HAM(x,y)$ is the number of bits on which $x$ and $y$ differ.
\end{definition}

If Alice has $x$ and Bob has $y$ then how many bits
do they need to communicate such that they both know $\HAM(x,y)$?
The trivial algorithm is to have Alice send $x$ (which takes $n$ bits)
and have Bob send $\HAM(x,y)$  (which takes $\ceil{\lg (n+1)}$ bits)
back to Alice. This takes $n+\ceil{\lg (n+1)}$ bits.
Pang and El Gamal~\cite{pang}
showed that this is essentially optimal.
In particular they showed that $\HAM$ requires 
at least $n +\lg(n+1-\sqrt n)$ bits to be communicated.
(See~\cite{abdel,commdoc,metzner,orlit} for more on
the communication complexity of $\HAM$.
See~\cite{securemulti} for how Alice and Bob can approximate
$\HAM$ without giving away too much information.)

What if Alice and Bob just want to know if $\HAM(x,y)\le a$?
\begin{definition}
Let $n\in\nat$. Let $a$ be such that $0\le a\le n-1$.
$\HAMa:\bits n \times \bits n \into \bit$ is the function

$$\HAMa(x,y) = \cases { 1 & if $\HAM(x,y)\le a$\cr
                      0 & otherwise.\cr
}
$$
\end{definition}

The problem $\HAMa$ has been studied by 
Yao~\cite{qfingerprinting} and Gavinsky et al~\cite{qpublic}.
Yao showed that there is an $O(a^2)$ public coin simultaneous
protocol for $\HAMa$ which yields (by Newman~\cite{Newman}, see also \cite{commcomp}) an
$O(a^2+\log n)$ private coin protocol and also
an $O(2^{a^2}\log n)$ quantum simulataneous message protocol with bounded error~\cite{qfingerprinting}.
Gavinsky et al. give an $O(a\log n)$ public coin
simultaneous protocol, which yields an $O(a\log n)$ private coin protocol.
For $a \gg \log n$ this is better than Yao's protocol.

All of the protocols mentioned have a small probability of error.
How much communication is needed for this problem if we demand no error?
There is, of course, the trivial $(n+1)$-bit protocol.
Is there a better one?

In this paper we show the following; in the list of results below, the
``$c$'' (in the ``$c \sqrt{n}$'' terms) is some positive absolute
constant.

\begin{enumerate}
\item\label{det:n-2}
For any $0 \leq a \leq n-1$, $\HAMa$ requires at least $n-2$ bits
in the deterministic model.
\item\label{det:n}
For $a\le c \sqrt{n}$, $\HAMa$ requires at least $n$ bits 
in the deterministic model.
\item\label{quant:n-2}
For any $0 \leq a \leq n-1$, $\HAMa$ requires at least $n-2$ bits
in the quantum model with Alice and Bob share an infinite number of EPR pairs,
using a classical channel, and always obtain the correct answer.
\item
For $a\le c \sqrt{n}$, $\HAMa$ requires at least $n$ bits 
in the quantum model in item \ref{quant:n-2}.
\item\label{quant:n/2minus1}
For any $0 \leq a \leq n-1$, $\HAMa$ requires at least $\frac{n}{2}-1$ bits
in the quantum model with Alice and Bob share an infinite number of EPR pairs,
using a quantum channel, and always obtain the correct answer.
\item\label{quant:n/2}
For $a\le c \sqrt{n}$, $\HAMa$ requires at least $n/2$ bits 
in the quantum model in item \ref{quant:n/2minus1}.
\end{enumerate}

Note that if $a=n$ then $(\forall x,y)[\HAMa(x,y)=1$,
hence we do not include that case.


What if Alice and Bob need to determine if $\HAM(x,y)=a$ or not?

\begin{definition}
Let $n\in\nat$. Let $a$ be such that $0\le a\le n$.
$\HAMea:\bits n \times \bits n \into \bit$ is the function

$$\HAMea(x,y) = \cases { 1 & if $\HAM(x,y)\le a$\cr
                      0 & otherwise.\cr
}
$$
\end{definition}

We show the exact same results for $\HAMea$ as we do for $\HAMa$.
There is one minor difference: for $\HAMa$ the $a=n$ case had complexity 0
since all pairs of strings differ on at most $n$ bits;
however, for $\HAMea$ the $a=n$ case has complexity $n+1$ as it is
equivalent to equality.

All our results use the known ``log rank'' lower bounds on
classical and quantum communication complexity: Lemmas~\ref{le:rank}
and \ref{le:qrank}. Our approach is to lower-bound the ranks of the
appropriate matrices, and then to invoke these known lower bounds.

\section{Definitions, Notations, and Useful Lemmas}

We give brief definitions of both classical and quantum communication
complexity. See~\cite{commcomp} for more details on classical, 
and~\cite{qsurvey} for more details on quantum.

\begin{definition}
Let $f$ be any function from $\bits n \times \bits n$ to $\bit $.
\begin{enumerate}
\item
A \textit{protocol } for computing $f(x,y)$, where Alice has $x$ and Bob has $y$,
is defined in the usual way (formally using decision trees).
At the end of the protocol both Alice and Bob know $f(x,y)$.
\item
$D(f)$ is the number of bits transmitted in the optimal deterministic protocol for $f$.
\item
$Q^*(f)$ is the number of bits transmitted in the optimal quantum protocol where
we allow Alice and Bob to share an infinite number of EPR pairs
and communicate over a quantum channel.
\item
$C^*(f)$ is the number of bits transmitted in the optimal quantum protocol where
we allow Alice and Bob to share an infinite number of EPR pairs
and communicate over a classical channel.
\item
$M_f$ is the $2^n \times 2^n$ matrix where the rows and columns are indexed
by $\bits n$ and the $(x,y)$-entry is $f(x,y)$.
\end{enumerate}
\end{definition}

Let $\lg$ denote the logarithm to the base two.
Also, as usual, if $x < y$, then ${x \choose y}$ is taken to be zero. 

The following theorem is due to
Mehlhorn and Schmidt~\cite{ranklower}; 
see also \cite{commcomp}.

\begin{lemma}\label{le:rank}
If $f:\bits n \times \bits n \into \bit $
then
$D(f)\ge \lg({\rm rank}(M_f))$.
\end{lemma}

Buhrman and de Wolf~\cite{qlogrank} proved a 
similar theorem for quantum communication complexity.

\begin{lemma}\label{le:qrank}
If $f:\bits n \times \bits n \into \bit $
then the following hold.
\begin{enumerate}
\item
$Q^*(f)\ge \frac{1}{2}\lg({\rm rank}(M_f))$.
\item
$C^*(f)\ge \lg({\rm rank}(M_f))$.
\end{enumerate}
\end{lemma}

\section{The Complexity $\HAMa$ for $a\le O(\sqrt n)$}\label{se:hamasq}
We start by presenting results for general $a$, and then specialize
to the case where $a \leq c \sqrt{n}$.

\begin{definition}
Let $M_a$ be $M_{\HAMa}$, the $2^n\times 2^n$ matrix representing $\HAMa$.
\end{definition}

\begin{lemma}
$M_a$ has $2^n$ orthogonal eigenvectors.
\end{lemma}

\begin{proof}
This follows from $M_a$ being symmetric.
\end{proof}

We know that $M_a$ has $2^n$ eigenvalues; however, some of them may be 0.
We prove that $M_a$ has few 0-eigenvalues.
This leads to a lower bound on $D(\HAMa)$ by Lemma~\ref{le:rank}.

\begin{definition}\label{de:vz}
Let $z\in \bits n$.
\begin{enumerate}
\item
$v_z \in R^{2^n}$ is defined by, for all $x\in \bits n$,  $v_z(x) = (-1)^{\sum_i x_i z_i }$. The entries $v_z(x)$ of $v_z$ are ordered in the natural
way: in the same order as the order of the index $x$
in the rows (and columns) of $M_a$. 
\item
We show that $v_z$ is an eigenvector of $M_a$. Once that is done
we let $\eig(z)$ be the eigenvalue of $M_a$ associated with $v_z$.
\end{enumerate}
\end{definition}

\begin{lemma}\label{le:main}~
\begin{enumerate}
\item The vectors $\{v_z: ~z\in \bits n\}$ are orthogonal.
\item
For all $z\in \bits n$, $v_z$ is an eigenvector of $M_a$.
\item
If $z$ has exactly $m$ 1's in it,
then 
$$eig(z)=\sum_{j=0}^a \SUM {m\choose k} {n-m \choose j-k} (-1)^k.$$
\end{enumerate}
\end{lemma}

\begin{proof}
The first assertion (orthogonality) follows by simple counting.
We now prove the final two assertions together.
Let $z\in \bits n$ have exactly $m$ ones in it.

Fix a row in $M_a$ that is indexed by $x\in \bits n$.
Denote this row by $R_x$.
We need the following notation:
\[
\begin{array}{rl}
L_a = & \{ y \mid \HAM(x,y) \le a \}\cr
E_j = & \{ y \mid \HAM(x,y) = j \}\cr
\end{array}
\]
We will show that $R_x \cdot v_z$ 
is a constant multiple (independent of $x$) times $v_z(x)$.
Now,
$$R_x\cdot v_z =  \sum_{y\in \bits n} \HAMa(x,y) v_z(y) = \sum_{y\in L_a} v_z(y) = \sum_{y\in L_a}  (-1)^{\sum_i y_iz_i }.$$
We would like to have this equal $b \times v_z(x)$ for some constant $b$.
We set it equal to $b\times v_z(x)$ and deduce what $b$ works.
So, suppose
$$b \times v_z(x) = \sum_{y\in L_a}  (-1)^{\sum_i y_iz_i }.$$

We have
\begin{eqnarray}
b & = & \frac{1}{v_z(x)} \sum_{y\in L_a}  (-1)^{\sum_i y_iz_i } \nonumber \\
& = & v_z(x) \sum_{y\in L_a}  (-1)^{\sum_i y_iz_i} \nonumber \\
& = & (-1)^{\sum_i x_iz_i} \sum_{y\in L_a}  (-1)^{\sum_i y_iz_i } \hbox{\ \ \ (by the definition of $v_z(x)$)} \nonumber \\
& = & \sum_{y\in L_a}  (-1)^{\sum_i (x_i+y_i)z_i} \nonumber \\
& = & \sum_{y\in L_a}  (-1)^{\sum_i |x_i-y_i|z_i } \hbox{\ \ \  (since $x_i+y_i \equiv |x_i-y_i| \pmod 2$) } \nonumber \\
& = & \sum_{j=0}^a \sum_{y\in E_j}  (-1)^{\sum_i |x_i-y_i|z_i } \hbox{\ \ \ (since $L_a = \bigcup_{j=0}^a E_j$)}. \label{eqn:b}
\end{eqnarray}

We partition $E_j$.
If $y\in E_j$ then
$x$ and $y$ differ in exactly $j$ places.
Some of those places $i$ are such that $z_i=1$.
Let $k$ be such that the number of places where $x_i\ne y_i$ and $z_i=1$.
\begin{description}
\item{Upper Bound on $k$:}
Since there are exactly $m$ places where $z_i=1$ we have $k\le m$.
Since there are exactly $j$ places where $x_i\ne y_i$ we have $k\le j$.
Hence $k\le\min\{j,m\}$.
\item{Lower Bound on $k$:}
Since there are exactly $n-m$ places where $z_i=0$, we have $j-k\le n-m$.
Hence $k\ge \max\{0,j+m-n\}$.
\end{description}

In summary, the only relevant $k$ are
$\max\{0,j+m-n\} \le k \le \min\{j,m\}$.
Fix $j$. For 

\noindent
$\max\{0,j+m-n\}\le k\le \min\{j,m\}$, 
let $D_{j,k}$ be defined as follows:
$$D_{j,k} = \{ y \mid ((y \in E_j) \wedge 
(\hbox{on exactly $k$ of the coordinates 
where $x_i\ne y_i$, we have $z_i = 1$})) \}.$$

Note that

$$E_j = \bigcup_{k=0}^{\min\{j,m\}} D_{j,k}$$
and $|D_{j,k}|= {m\choose k} {n-m \choose j-k}$. So, by (\ref{eqn:b}),
$$
b = \sum_{j=0}^a \sum_{y\in E_j}  (-1)^{\sum_i |x_i-y_i|z_i }
  = \sum_{j=0}^a \SUM \sum_{y\in D_{j,k}} (-1)^{\sum_i |x_i-y_i|z_i }.
$$

By the definition of $D_{j,k}$ we know that for exactly $k$ of the values of $i$
we have both $|x_i-y_i|=1$ and $z_i=1$. On all other values one of the two
quantities is 0. Hence we have the following:
\begin{eqnarray*}
b & = & \sum_{j=0}^a \SUM  \sum_{y\in D_{j,k}} (-1)^k \\
& = & \sum_{j=0}^a \SUM  |D_{j,k}| (-1)^k \\
& = & \sum_{j=0}^a \SUM  {m\choose k} {n-m \choose j-k} (-1)^k.
\end{eqnarray*}

Notice that $b$ is independent of $x$ and is of the form required.
\end{proof}

\begin{definition}
Let 
$$F(a,n,m)= \sum_{j=0}^a \SUM {m\choose k} {n-m \choose j-k} (-1)^k.$$
\end{definition}


The following lemma will be used in this section to obtain a lower bound
when $a=O(\sqrt n)$, and in Section~\ref{se:gen} to obtain a lower bound for general $a$.

\begin{lemma}\label{le:uslea}~
\begin{enumerate}
\item
$D(\HAMa) \ge \lg \sum_{m: F(a,n,m)\ne 0 } { n \choose m }.$
\item
$Q^*(\HAMa) \ge \frac{1}{2}\lg \sum_{m: F(a,n,m)\ne 0 } { n \choose m }.$
\item
$C^*(\HAMa) \ge \lg \sum_{m: F(a,n,m)\ne 0 } { n \choose m }.$
\end{enumerate}
\end{lemma}

\begin{proof}
By Lemma~\ref{le:main}, the eigenvector $v_z$ has a nonzero eigenvalue
if $v_z$ has $m$ 1's and $F(a,n,m)\ne0$.
The rank of $M_a$ is the number of nonzero eigenvalues that correspond
to linearly independent eigenvectors. 
This is $\sum_{m: F(a,n,m)\ne 0 } { n \choose m }.$
The theorem follows from Lemmas~\ref{le:rank} and \ref{le:qrank}.
\end{proof}


\begin{lemma}\label{le:lea}
The number of values of $m$ for which $F(a,n,m)=0$ is
$\le a$.
\end{lemma}

\begin{proof}
View  the double summation $F(a,n,m)$
%$$\sum_{j=0}^a \SUM {m\choose k} {n-m \choose j-k} (-1)^k$$
as a  polynomial in $m$. The $j$th summand has degree $k+(j-k)=j$.
Since $j\le a$ the entire sum can be written as a polynomial in
$m$ of degree $a$. This has at most $a$ roots.
\end{proof}

\begin{theorem}\label{th:main}
There is a constant $c > 0$ such that if $a\le c\sqrt n$
then the following hold.
\begin{enumerate}
\item
$D(\HAMa) \ge n$.
\item
$Q^*(\HAMa) \ge n/2$.
\item
$C^*(\HAMa)\ge n$.
\end{enumerate}
\end{theorem}

\begin{proof}
By Lemma~\ref{le:uslea}
$D(f),Q^*(f) \ge \lg (\sum_{m: F(a,n,m)\ne 0 } { n \choose m })$ and
$C^*(f) \ge \frac{1}{2}\lg (\sum_{m: F(a,n,m)\ne 0 } { n \choose m })$.

Note that
$$2^n = \sum_{m: F(a,n,m)\ne 0 } { n \choose m } +\sum_{m: F(a,n,m)=0 } { n\choose m}.$$
By Lemma~\ref{le:lea} $|\{ m : F(a,n,m)=0 \}|\le a$. Hence,
$$\sum_{m: F(a,n,m)=0 } { n\choose m} \le |\{ m : F(a,n,m)=0 \}|\cdot\max_{0\le m\le n} {n\choose m}
\le a{ n \choose {n/2} } \le \frac{a2^n}{\sqrt n}.$$
So, if $a\le \frac{1}{4}\sqrt n$, then 
$$\sum_{m: F(a,n,m)\ne 0 } { n \choose m } \ge 2^n - \frac{a2^n}{\sqrt n}
\geq 2^n - 2^{n-2}.$$
Hence,
$$\lg \left(\sum_{m: F(a,n,m)\ne 0 } { n \choose m }\right) \ge 
\lg(2^n - 2^{n-2}); ~~
\mathrm{i.e.}, ~
\left\lceil \lg \left(\sum_{m: F(a,n,m)\ne 0 } { n \choose m }\right) 
\right\rceil \ge n.$$
\end{proof}

\section{The Complexity of $\HAMea$ for $a\le O(\sqrt{n})$}\label{se:hameasq}
We again start by deducing results for general $a$, and then specialize
to the case where $a \leq c \sqrt{n}$.

\begin{definition}
Let $M_{=a}$ be $M_{\HAMea}$, the $2^n\times 2^n$ matrix representing $\HAMea$.
\end{definition}

The vectors $v_z$ are the same ones defined in Definition~\ref{de:vz}.
We show that $v_z$ is an eigenvector of $M$. Once that is done
we let $\eig(z)$ be the eigenvalue of $M$ associated to $z$.

The lemmas needed, and the final theorem,
are very similar (in fact easier) to those
in the prior section. Hence we just
state the needed lemmas and final theorem.

\begin{lemma}\label{le:maina}~
\begin{enumerate}
\item
For all $z\in \bits n$ $v_z$ is an eigenvector of $M_{=a}$.
\item
If $z$ has exactly $m$ 1's in it
then 
$$eig(z)=\SUMa {m\choose k} {n-m \choose a-k} (-1)^k.$$
\end{enumerate}
\end{lemma}

\begin{definition}
\label{defn:f}
$$f(a,n,m)= \SUMa {m\choose k} {n-m \choose a-k} (-1)^k.$$
\end{definition}

Note, from our convention that 
``if $x < y$, then ${x \choose y}$ is taken to be zero'', that
we can also write
\[ f(a,n,m)= \sum_{k=0}^{a} {m\choose k} {n-m \choose a-k} (-1)^k. \]

The following lemma will be used in this section to obtain a lower bound
when $a=O(\sqrt n)$, and in Section~\ref{se:gen} to obtain a lower bound for general $a$.

\begin{lemma}\label{le:useqa}~
\begin{enumerate}
\item
$D(\HAMea) \ge \lg \sum_{m: f(a,n,m)\ne 0 } { n \choose m }.$
\item
$Q^*(\HAMea) \ge \lg \sum_{m: f(a,n,m)\ne 0 } { n \choose m }.$
\item
$C^*(\HAMea) \ge \frac{1}{2} \cdot \lg \sum_{m: f(a,n,m)\ne 0 } { n \choose m }.$
\end{enumerate}
\end{lemma}

\begin{lemma}\label{le:ea}
The number of values of $m$ for which $f(a,n,m)=0$ is
$\le a$.
\end{lemma}

\begin{theorem}\label{th:maine}
There is a constant $c > 0$ such that if $a\le c\sqrt n$
then the following hold.
\begin{enumerate}
\item
$D(\HAMea) \ge n$.
\item
$Q^*(\HAMea) \ge n/2$.
\item
$C^*(\HAMea)\ge n$.
\end{enumerate}
\end{theorem}

\section{The Complexity of $\HAMa$ and $\HAMea$ for General $a$}\label{se:gen}
We now consider the case of general $a$. As above,
we will show that $F(a,m,n)$ and $f(a,m,n)$ are nonzero for many values of
$m$. This will imply that the matrices $M_a$
and $M_{=a}$ have high rank,  hence $\HAMa$ and $\HAMea$
have high communication complexity.
 We will use
 general generating-function methods to derive facts about these sums. A good
 source on generating functions is~\cite{wilfgen}. 

One of our main
results will be Lemma~\ref{le:singlesum}, which states that if
$0 \leq a \leq m < n$, then ``$f(a,m,n)=0$'' implies
``$f(a,m+1,n) \neq 0$''. 
The idea behind our proof of Lemma~\ref{le:singlesum} will
be the following: we will show a relationship
between the sum $f(a,m,n)$ and a certain new sum $h(a,m,n)$. Then we will
derive generating functions for $f$ and $h$, and translate this relationship
into a relation between their generating functions. Finally, we will show
that this relation cannot hold under the assumption that
$f(a,m,n)=f(a,m+1,n)=0$, thus reaching a contradiction. Some auxiliary
results needed for this are now developed in Section~\ref{sec:aux}.

\subsection{Auxiliary Notation and Results}
\label{sec:aux}
\begin{notation}
$[x^b]g(x)$ is the coefficient of $x^b$ in the power series
 expansion of $g(x)$ around $x_0=0$.
\end{notation}
\begin{notation}
$t^{(i)}(x)$ is the $i$'th derivative of $t(x)$.
\end{notation}

We will make use of the following lemma, which follows by an easy induction
on $i$:

\begin{lemma}
\label{lem:deriv}
Let $t(x)$ be an infinitely differentiable function.
Let $T_1(x)=(x-1)t(x)$, and 

\noindent
$T_2(x)=(x+1)t(x)$. Then for any $i\geq 1$:\\
$T_1^{(i)}(x)=(x-1)t^{(i)} + i\cdot t^{(i-1)}(x)$\\
$T_2^{(i)}(x)=(x+1)t^{(i)} + i\cdot t^{(i-1)}(x)$
\end{lemma}

For the rest of Section~\ref{sec:aux}, the integers $a, m, n$ are
arbitrary subject to the constraint $0 \leq a \leq m \leq n$,
unless specified otherwise. 

\begin{definition}~
\begin{enumerate}
\item
$h(a,m,n)=\sum_{i=0}^{a} {m \choose i}{n-m \choose a-i}\frac{(-1)^i}{m-i+1}$.
\item
$g(x)=\frac{x^{m+1} - (x-1)^{m+1}}{m+1}\cdot (x+1)^{n-m}$. 
\end{enumerate}
\end{definition}

 We will show an interesting connection between $h$ and $f$.

\begin{claim}\label{cl:one}
Suppose $f(a,m,n)=0$. Then $f(a,m+1,n)=0$ iff $h(a,m,n)=0$.
\end{claim}

\begin{proof}
\[
\begin{array}{rl}
 f(a,m+1,n)=&\sum_{i=0}^{a} {m+1 \choose i}{n-m-1 \choose a-i}(-1)^i\cr
         =&\frac{m+1}{n-m}\sum_{i=0}^{a} {m \choose i}{n-m \choose a-i}(-1)^i
\cdot \frac{n-m-a+i}{m-i+1}\cr
         =&\frac{m+1}{n-m}((n+1-a)\sum_{i=0}^{a} {m \choose i}{n-m \choose a-i}\frac{(-1)^i}{m-i+1})-\sum_{i=0}^{a} {m \choose i}{n-m \choose a-i}(-1)^i)\cr
         =&\frac{m+1}{n-m}((n+1-a)h(a,m,n)-f(a,m,n))\cr
\end{array}
\]
Thus, if $f(a,m,n)=0$,
 then $f(a,m+1,n)=0$ iff $h(a,m,n)=0$.
\end{proof}

We next show a connection between $g(x)$ and $h$.

\begin{claim}\label{cl:two}
$h(a,m,n)=(-1)^m\cdot [x^a]g(x)$.
\end{claim}

\begin{proof}

\[
\begin{array}{rl}
 g(x)=&\frac{x^{m+1} - (x-1)^{m+1}}{m+1}\cdot (x+1)^{n-m}\cr
     =&\frac{x^{m+1} - \sum_{i=0}^{m+1}{m+1 \choose i}x^i(-1)^{m+1-i}}{m+1}\cdot (x+1)^{n-m}\cr
     =&(-1)^m\sum_{i=0}^{m}{m \choose i}x^i\frac{(-1)^i}{m+1-i}\cdot (x+1)^{n-m}\cr
     =&(-1)^m\sum_{i=0}^{m}{m \choose i}x^i\frac{(-1)^i}{m+1-i}\cdot\sum_{j=0}^{n-m}{n-m \choose j}x^j\cr
\end{array}
\]
 Therefore, $h(a,m,n)=(-1)^m\cdot [x^a]g(x)$. 
\end{proof}

Next, define an auxiliary function $\phi(u,v,w)$ as the $w$'th derivative
 of the function $(x+1)^u(x-1)^v$ evaluated at $x=0$. We now relate
$\phi$ and $h$.

\begin{claim}\label{cl:three}
$h(a,m,n)=0$ iff $\phi(n-m, m+1, a) = 0$.
\end{claim}

\begin{proof}

By Claim~\ref{cl:two}

\[
\begin{array}{rl}
h(a,m,n)=&(-1)^m\cdot [x^a]g(x)\cr
        =&\frac{(-1)^m}{m+1}([x^a](x^{m+1}\cdot (x+1)^{n-m})-[x^a]((x-1)^{m+1}\cdot (x+1)^{n-m})).\cr
\end{array}
\]

 But $[x^a](x^{m+1}\cdot (x+1)^{n-m})=0$, since $a<m+1$. So

\[
\begin{array}{rl}
 h(a,m,n)=&\frac{(-1)^{m+1}}{m+1}[x^a]((x-1)^{m+1}\cdot (x+1)^{n-m})\cr
         =&\frac{(-1)^{m+1}}{m+1}\cdot\frac{\phi(n-m, m+1, a)}{a!}.\cr
\end{array}
\]

Thus, $h(a,m,n)=0$ iff $\phi(n-m, m+1, a) = 0$.
\end{proof}

Now we can relate the zeroes of $f$ with those of $\phi$:

\begin{claim}\label{cl:four}
$f(a,m,n)=0$ iff $\phi(n-m, m, a)=0$.
\end{claim}

\begin{proof}

\[
\begin{array}{rl}
(x-1)^m(x+1)^{n-m}=&\sum_{i=0}^m {m \choose i}x^i(-1)^{m-i} \cdot \sum_{j=0}^{n-m}{n-m \choose j}x^j\cr
                  =&(-1)^m\sum_{i=0}^m {m \choose i}x^i(-1)^i \cdot \sum_{j=0}^{n-m}{n-m \choose j}x^j\cr
                  =&(-1)^m\sum_{b=0}^{n}\sum_{k=0}^b {m \choose k}{n-m \choose b-k}(-1)^k x^b\cr
                  =&(-1)^m\sum_{b=0}^{n} f(b,m,n)\cdot x^b.\cr
\end{array}
\]

 So $f(a,m,n)=\frac{(-1)^m}{a!}\cdot\phi(n-m, m, a)$, thus
 $f(a,m,n)=0$ iff $\phi(n-m, m, a)=0$.
\end{proof}


\begin{claim}\label{cl:five}
Suppose $m < n$ and
$\phi(n-m, m, a)=0$. Then 

$$\phi(n-m-1, m+1, a)=0 \hbox{ iff } \phi(n-m, m+1, a)=0.$$
\end{claim}

\begin{proof}
This claim follows from 
Claims~\ref{cl:one}, \ref{cl:three}, and \ref{cl:four}.
\end{proof}

\medskip 
We are now able to prove a recursive relation between values of $\phi$:

\begin{claim}\label{cl:six}
If $k>0$, $a > 0$, and $\phi(k, m, a)=\phi(k,m,a-1)=0$, then

\noindent
 $\phi(k-1, m, a)=\phi(k-1,m,a-1)=0$. 
\end{claim}

\begin{proof} 
Suppose $\phi(k, m, a)=\phi(k,m,a-1)=0$. By Lemma~\ref{lem:deriv}, 
\begin{equation}
\label{eqn:phi-k-m+1}
\phi(k,m+1,a)=-\phi(k,m,a)+a\cdot\phi(k,m,a-1)=0.
\end{equation}

By Claim~\ref{cl:five}, since $\phi(k, m, a)=0$,
 we know that 
$$\phi(k-1,m+1,a)=0 \hbox{ iff }\phi(k,m+1,a)=0.$$
Now, (\ref{eqn:phi-k-m+1}) yields
 $\phi(k-1,m+1,a)=0$. Applying Lemma~\ref{lem:deriv} again, we obtain:

\[
\begin{array}{rl}
 0 = & \phi(k-1,m+1,a)=-\phi(k-1,m,a)+ a \cdot\phi(k-1,m,a-1); \cr
 0  =& \phi(k,m,a)=\phi(k-1,m,a)+ a \cdot \phi(k-1,m,a-1)\cr
\end{array}
\]
Solving the equations, we get 
$$\phi(k-1,m,a) = \phi(k-1,m,a-1)=0.$$
Thus the claim is proved.
\end{proof}

\subsection{The main results}
\label{sec:main-results}
We are now ready to prove our main lemma.

\begin{lemma}
\label{le:singlesum}
Let $0 \leq a \leq m < n$, and suppose $f(a,m,n)=0$. Then $f(a,m+1,n) \neq 0$.
\end{lemma}

\begin{proof}
The lemma holds trivially for $a = 0$, since both
$f(a,m,n)$ and $f(a,m+1,n)$ are nonzero if $a = 0$.
So suppose $a \geq 1$. 
Suppose $f(a,m,n)=f(a,m+1,n)=0$.
Then by Claims~\ref{cl:four} and \ref{cl:five}, we know that
$$\phi(n-m, m, a)=\phi(n-m-1, m+1, a)=\phi(n-m, m+1, a)=0.$$ 
By Lemma~\ref{lem:deriv}, 
$$\phi(n-m, m+1, a)= -\phi(n-m,m,a)+a\cdot\phi(n-m,m,a-1),$$
i.e., $\phi(n-m,m,a-1) = 0$.
 Hence $\phi(n-m,m,a-1)= \phi(n-m,m,a)=0$. Now, an iterative
application of Claim~\ref{cl:six} eventually yields $\phi(0,m,a)=\phi(0,m,a-1)=0$. By
 definition, $\phi(0,m,a)$ is the $a$'th derivative of
 $$(x-1)^m=\sum_{i=0}^{m} {m \choose i}x^i(-1)^{m-i}$$
 evaluated
 at $x=0$. But $m \geq a$, so this is clearly not zero. Thus we have
 reached a contradiction, and Lemma~\ref{le:singlesum} is proved.
\end{proof}

\begin{theorem}
\label{thm:eqcomplexity}
For large enough $n$ and all $0 \leq a \leq n$ the following hold.
\begin{enumerate}
\item
$D(\HAMea) \geq n-2$.
\item
$Q^*(\HAMea)\geq \frac{n}{2}-1$.
\item
$C^*(\HAMea)\ge n-2$.
\end{enumerate}
\end{theorem}

\begin{proof}
By Lemma~\ref{le:useqa},
$$D(f), C^*(f) \ge \lg(\sum_{m: f(a,m,n)\ne 0} { n \choose m })$$
and
$$Q^*(f) \ge \frac{1}{2}\lg(\sum_{m: f(a,m,n)\ne 0} { n \choose m }).$$

First suppose $a \leq n/2$. We have 
\begin{equation}
\label{eqn:small-a-large-m}
\sum_{m: f(a,m,n)\ne 0} {n \choose m} \geq
\sum_{m \geq n/2: f(a,m,n)\ne 0} {n \choose m}.
\end{equation}
Let us lower-bound the r.h.s.\ of (\ref{eqn:small-a-large-m}). First
of all, since the r.h.s.\ of (\ref{eqn:small-a-large-m}) works in the
regime where $m \geq n/2 \geq a$, Lemma~\ref{le:singlesum} shows
that no two consecutive values of $m$ in this range satisfy the
condition ``$f(a,m,n) = 0$''. Also, for $m \geq n/2$,
${n \choose m}$ is a non-increasing function of $m$.
Thus, if we imagine an adversary whose
task is to keep the r.h.s.\ of (\ref{eqn:small-a-large-m}) as small
as possible, the adversary's best strategy, in our regime
where $m \geq n/2$, is to make $f(a,m,n) = 0$ exactly when
$m \in S$, where
\begin{equation}
\label{eqn:S}
S \doteq \{\lceil n/2 \rceil, \lceil n/2 \rceil + 2, 
\lceil n/2 \rceil + 4, \ldots \}. 
\end{equation}

Now, 
\begin{equation}
\label{eqn:m-large}
2^{n-1} \leq \sum_{m \geq n/2} {n \choose m} \leq
2^{n-1} + O(2^n / \sqrt{n}). 
\end{equation}
(We need the second inequality to handle the case where $n$ is even.)
Also, recall that an $(1 - o(1))$ fraction of the
sum $\sum_{m \geq n/2} {n \choose m}$ is obtained from the range
$n/2 \leq m \leq n/2 + \sqrt{n \log n}$, for instance. 
(Here and in what follows, ``$o(1)$'' denotes a function of $n$ that
goes to zero as $n$ increases.) In this range,
the values of ${n \choose m}$ for any two consecutive values of $m$ are
within $(1 + o(1))$ of each other. In conjunction with (\ref{eqn:m-large}),
this shows that
\[ \sum_{m \geq n/2: f(a,m,n)\ne 0} {n \choose m}
\geq \sum_{m \geq n/2: m \not\in S} {n \choose m} \geq
(1/2 - o(1)) 2^{n-1}. \]
Thus,
\[ \left\lceil \lg\left(\sum_{m \geq n/2: f(a,m,n)\ne 0} {n \choose m}\right)
\right\rceil \geq n-2, \]
completing the proof for the case where $a \leq n/2$.

Now we apply symmetry to the case $a> n/2$: note that Alice can
reduce the problem with parameter $a$ to the problem with parameter
$n - a$, simply by complementing each bit of her input $x$. Thus,
the same communication complexity results hold for the case $a > n/2$.
\end{proof}

\begin{lemma}\label{le:zero}
Let $0 \leq a < m < n$, and suppose $F(a,m,n)=0$. Then $F(a, m+1, n) \neq 0$.
\end{lemma}

\begin{proof}
We have
 $f(j,m,n)=(-1)^m[x^j]((x-1)^m(x+1)^{n-m})$. By definition,
\[
\begin{array}{rl}
 F(a,m,n)=&\sum_{j=0}^a f(j,m,n)\cr
         =&(-1)^m \sum_{j=0}^a [x^j]((x-1)^m(x+1)^{n-m})\cr
         =&(-1)^m [x^a]((x-1)^m(x+1)^{n-m}\cdot\sum_{j=0}^{\infty}x^j)\cr
         =&(-1)^m [x^a]((x-1)^m(x+1)^{n-m}\cdot\frac{1}{1-x})\cr
         =&(-1)^{m-1} [x^a]((x-1)^{m-1}(x+1)^{n-m})=f(a,m-1,n-1).\cr
\end{array}
\]
 So $F(a,m,n)=F(a,m+1,n)=0$ iff
 $f(a,m-1,n-1)=f(a,m,n-1)=0$. But the latter is impossible
 by Lemma~\ref{le:singlesum}, thus the lemma is proved.
\end{proof}

\begin{theorem}
For large enough $n$ and all $0 \leq a \leq n-1$, 
the following hold.
\begin{enumerate}
\item
$D(\HAMa) \geq n-2$.
\item
$Q^*(\HAMa) \geq \frac{n}{2}-1$.
\item
$C^*(\HAMa) \geq n-2$.
\end{enumerate}
\end{theorem}

\begin{proof}
The proof is identical to that of Theorem~\ref{thm:eqcomplexity}
except for one point. In that proof we obtained the $a> n/2$
case easily from the $a\le n/2$ case. Here it is also easy
but needs a different proof. Let $a> n/2$ and, for all $x\in \bits n$,
let $\xbar$ be obtained from $x$ by flipping every single bit.
Note that

$\HAMa(x,y)=1$ iff $\HAM(x,y)\le a$ iff $\HAM(\xbar,y)\ge n-a$
iff NOT($\HAM(\xbar,y)\le (n-a)-1$ iff
$\HAM_{n-a-1}(\xbar,y)=1$.

Since $n-a-1 \le n/2$ we have that a lower bound for the $a\le n/2$
case implies a lower bound for the $a>n/2$ case.
\end{proof}



\section{Open Problems}

We make the following conjectures.

\begin{enumerate}
\item
For all $n$, for all $a$, $0\le a\le n-1$, $D(\HAMa), C^*(\HAMa), Q^*(\HAMa) \ge n+1$.
\item
For all $n$, for all $a$, $0\le a\le n$, $D(\HAMea), C^*(\HAMea), Q^*(\HAMea) \ge n+1$.
\end{enumerate}


\begin{thebibliography}{10}

\bibitem{abdel}
K.~Abdel-Ghaffar and A.~E. Ababdi.
\newblock An optimal strategy for comparing file copies.
\newblock \textit{IEEE Transactions on Parallel and Distributed Systems},
  5:87--93, 1994.

\bibitem{qlogrank}
H.~Buhrman and R.~de~Wolf.
\newblock Communication complexity lower bounds by polynomials.
\newblock In \textit{Proc. of the 16th IEEE Conf on Complexity Theory}. IEEE
  Computer Society Press, 2001.

\bibitem{commdoc}
G.~Cormode, M.~Paterson, S.~Sahinalp, and U.~Vishkin.
\newblock Communication complexity of document exchange.
\newblock In \textit{Proc. of the 11th ACM Sym. on Discrete Algorithms}, 2000.

\bibitem{qsurvey}
R.~de~Wolf.
\newblock Quantum communication and complexity.
\newblock \textit{Theoretical Comput. Sci.}, 12:337--353, 2002.

\bibitem{securemulti}
J.~Feigenbaum, Y.~Ishai, T.~Malkin, K.~Nissim, M.~Strauss, and R.~Wright.
\newblock Secure multiparty computation of approximations.
\newblock In \textit{Proc. of the 28th ICALP (LNCS 2076)}, volume 2076 of {\em
  Lecture Notes in Computer Science}, pages 927--938, Berlin, 2001.
  Springer-Verlag.

\bibitem{qpublic}
D.~Gavinsky, J.~Kempe, and R.~de~Wolf.
\newblock Quantum communication cannot simulate a public coin, 2004.
\newblock arxiv.org/abs/quant-ph/0411051.

\bibitem{commcomp}
E.~Kushilevitz and N.~Nisan.
\newblock \textit{Communication Complexity}.
\newblock Cambridge University Press, 1997.

\bibitem{ranklower}
K.~Mehlhorn and E.~Schmidt.
\newblock Las {V}egas is better than determinism for {VLSI} and distributed
  systems.
\newblock In \textit{Proc. of the 14th ACM Sym. on Theory of Computing}, pages
  330--337, 1982.

\bibitem{metzner}
J.~Metzner.
\newblock Efficient replicated remote file comparison.
\newblock \textit{IEEE Transactions on Computers}, 40:651--659, 1991.

\bibitem{Newman}
I.~Newman.
\newblock Private vs. common random bits in communication complexity.
\newblock \textit{Inf. Process. Lett.}, 39:67--71, 1991.

\bibitem{orlit}
A.~Orlitsky.
\newblock Interactive communication: balanced distributions, correlated files,
  and average-case complexity.
\newblock In \textit{Proc. of the 32st IEEE Sym. on Found. of Comp. Sci.}, pages
  228--238, 1991.

\bibitem{pang}
K.~Pang and A.~E. Gamal.
\newblock Communication complexity of computing the {H}amming distance.
\newblock \textit{SIAM Journal of Computing}, 15, 1986.

\bibitem{wilfgen}
H.~Wilf.
\newblock \textit{Generatingfunctionology}.
\newblock Academic Press, 1994.

\bibitem{qfingerprinting}
A.~Yao.
\newblock On the power of quantum fingerprinting.
\newblock In \textit{Proc. of the 35th ACM Sym. on Theory of Computing}, 2003.

\end{thebibliography}



\end{document}

cs0411076.extracted_bib
\begin{thebibliography}{10}

\bibitem{abdel}
K.~Abdel-Ghaffar and A.~E. Ababdi.
\newblock An optimal strategy for comparing file copies.
\newblock \textit{IEEE Transactions on Parallel and Distributed Systems},
  5:87--93, 1994.

\bibitem{qlogrank}
H.~Buhrman and R.~de~Wolf.
\newblock Communication complexity lower bounds by polynomials.
\newblock In \textit{Proc. of the 16th IEEE Conf on Complexity Theory}. IEEE
  Computer Society Press, 2001.

\bibitem{commdoc}
G.~Cormode, M.~Paterson, S.~Sahinalp, and U.~Vishkin.
\newblock Communication complexity of document exchange.
\newblock In \textit{Proc. of the 11th ACM Sym. on Discrete Algorithms}, 2000.

\bibitem{qsurvey}
R.~de~Wolf.
\newblock Quantum communication and complexity.
\newblock \textit{Theoretical Comput. Sci.}, 12:337--353, 2002.

\bibitem{securemulti}
J.~Feigenbaum, Y.~Ishai, T.~Malkin, K.~Nissim, M.~Strauss, and R.~Wright.
\newblock Secure multiparty computation of approximations.
\newblock In \textit{Proc. of the 28th ICALP (LNCS 2076)}, volume 2076 of {\em
  Lecture Notes in Computer Science}, pages 927--938, Berlin, 2001.
  Springer-Verlag.

\bibitem{qpublic}
D.~Gavinsky, J.~Kempe, and R.~de~Wolf.
\newblock Quantum communication cannot simulate a public coin, 2004.
\newblock arxiv.org/abs/quant-ph/0411051.

\bibitem{commcomp}
E.~Kushilevitz and N.~Nisan.
\newblock \textit{Communication Complexity}.
\newblock Cambridge University Press, 1997.

\bibitem{ranklower}
K.~Mehlhorn and E.~Schmidt.
\newblock Las {V}egas is better than determinism for {VLSI} and distributed
  systems.
\newblock In \textit{Proc. of the 14th ACM Sym. on Theory of Computing}, pages
  330--337, 1982.

\bibitem{metzner}
J.~Metzner.
\newblock Efficient replicated remote file comparison.
\newblock \textit{IEEE Transactions on Computers}, 40:651--659, 1991.

\bibitem{Newman}
I.~Newman.
\newblock Private vs. common random bits in communication complexity.
\newblock \textit{Inf. Process. Lett.}, 39:67--71, 1991.

\bibitem{orlit}
A.~Orlitsky.
\newblock Interactive communication: balanced distributions, correlated files,
  and average-case complexity.
\newblock In \textit{Proc. of the 32st IEEE Sym. on Found. of Comp. Sci.}, pages
  228--238, 1991.

\bibitem{pang}
K.~Pang and A.~E. Gamal.
\newblock Communication complexity of computing the {H}amming distance.
\newblock \textit{SIAM Journal of Computing}, 15, 1986.

\bibitem{wilfgen}
H.~Wilf.
\newblock \textit{Generatingfunctionology}.
\newblock Academic Press, 1994.

\bibitem{qfingerprinting}
A.~Yao.
\newblock On the power of quantum fingerprinting.
\newblock In \textit{Proc. of the 35th ACM Sym. on Theory of Computing}, 2003.

\end{thebibliography}