L2.tex 17.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
\documentclass{tufte-handout} % use larger type; default would be 10pt

\usepackage[utf8]{inputenc} % set input encoding (not needed with XeLaTeX)
\usepackage{geometry} % to change the page dimensions

\usepackage{graphicx} 
\usepackage{amsmath,amsthm,url}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{proposition}{Proposition}
%%% PACKAGES
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim

\usepackage[draft,inline,nomargin,index]{fixme}
\fxsetup{theme=colorsig,mode=multiuser,inlineface=\sffamily,envface=\itshape}
\FXRegisterAuthor{su}{asu}{Suresh}
\FXRegisterAuthor{ro}{aro}{Robert}


\newcommand{\determin}[1]{\mathcal{D}\left(#1\right)}
\newcommand{\randR}[1]{\mathcal{R}\left(#1\right)}
\newcommand{\equ}{\mathcal{E\!Q}}
26
\newcommand{\disjoint}{\ensuremath{\mathcal{DISJ}}}
27
\newcommand{\mP}{\mathcal{P}}
28
\newcommand{\gt}{\textsc{GT}}
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
%%% END Article customizations

%%% The "real" document content comes below...

\title{CS 7931: Lecture 2}
\author{Robert Christensen}
%\date{} % Activate to display a given date or no date (if empty),
         % otherwise the current date is printed 

\begin{document}
\maketitle

% Why does the size matter with median computations?
%
%The rational that you remove the same amount from both sides
%only matters if it removes the same fraction at each iteration.
%Equality is necessary $|n_{\text{Alice}}| \equal |n_{\text{Bob}}|$,
%almost equal does not work.

\section{A review of Equality}

% recording ~4:50
If you look at the set of inputs that end up at any leaf of
the protocol tree, it is a combinatorial rectangle.  If we say this,
we know all the elements in the rectangle must have the same answer.
The protocol tree can be represented as a matrix and we want to color
the matrix with monochromatic rectangles.

\begin{marginfigure}
\centering
\includegraphics{figs/equal_rectangle}
\end{marginfigure}

If we look at the example of equality, there is no way to cover
multiple `$1$' answers in a single rectangle, so each `$1$' must
be in its own rectangle.  Since there are $2^n$ leafs with a `$1$'
and each element must be in its own rectangle. The tree must have
depth at least $\log$ of that, so for this example equality must have

\begin{equation*}
\determin{\equ} = \log 2^n = n \log 2 = O(n)
\end{equation*}

72 73 74 75
% Most lower bounds are proved using this method.  The model is
% investigated in detail to understand what limitations exist
% for what shapes the model can create in the protocol tree.
% We use this information to trap the model into a difficulty.
76 77 78 79 80 81 82 83 84 85 86

% recording ~8:00
\paragraph{Fooling set argument}

The fooling set argument is one of the basic methods for proving
lower bounds in communication complexity.  We are constructing
a witness set which is hard to cover.  In other words, they can
not be placed in the same combinatorial rectangle.

\begin{definition}
\label{def:fooling}
87 88
A fooling set is a subset $S \subseteq X \times Y$ of inputs and a fixed value
$z \in \{0,1\}$ such that:
89 90

\begin{itemize}
91
\item $(x,y) \in  S \implies f(x,y) = Z$
92

93
\item if $(x_1, y_1)$ and $(x_2, y_2) \in S$ \\ 
94 95 96 97 98 99 100
  then either $f(x_2, y_1) \neq Z$ or $f(x_1, y_2) \neq Z$
\end{itemize}
\end{definition}

% recording ~10:45
\begin{lemma}
\label{lem:fooling}
101
If S in a fooling set for $f$ then
102 103 104 105 106
\begin{equation*}
 \determin{f} \geq \log_2{|S|}
\end{equation*}
\end{lemma}

107 108 109 110 111 112 113
The proof of the above lemma follows essentially from the second property
above. It guarantees that any two elements of $S$ define a combinatorial
rectangle that is not monochromatic, and so no two elements of $S$ can be
covered by the same leaf. 

Note that $S$ is only defined with respect to the function $f$ and is
independent of any algorithm used to calculate $f$. 
114 115 116 117

Our only job for using the fooling set is to find a set which
satisfies the properties in definition \ref{def:fooling}.  We look
a the size of the set $S$ which comes from the definition and
118
we use \autoref{lem:fooling} to get the lower bound.
119

120
\paragraph{Example: \textsc{Greater than}}
121 122
% recording ~14:30

123
We will define the function $\gt(x,y)$ to be
124 125

\begin{equation*}
126
 \gt(x,y) = \left\{ 
127 128 129 130 131 132 133 134 135
  \begin{array}{l l}
    1 & \quad \text{if } x \geq y\\
    0 & \quad \text{otherwise}
  \end{array} \right.
\end{equation*}

\begin{marginfigure}
\centering
\includegraphics{figs/ge_matrix_2}
136
\caption{Example matrix for $\gt(x,y)$ when $|x| = |y| = 5$ with fooling set elements of size 2 drawn.}
137
\end{marginfigure}
138 139 140
%\sunote{Better to have just the figure as a PDF and use the caption for the
%  text. This allows you to use the \gt command for the function name, to get a
%  consistent look.}
141

142

143
According to the definition of $\gt(x,y)$ the lower triangle
144 145 146 147 148 149 150 151 152 153 154 155
will be `$1$'.  The remaining values in the upper right
corner will be `$0$'.

In the example shown here, we are including the elements
along the diagonal which have the value $1$ except for
the `upper right' corner, which has a value $0$.

%We can create a fooling set along the diagonal.  All
%the elements along the diagonal have the value $1$.
%The `upper right' corner is $0$.  We also include the
%elements where all the elements are $0$ exept the 

156
The size of the fooling set for $\gt(x,y)$ is $|S|=2^n$.
157 158 159 160
Now we know the value of $|S|$, $\determin{gt(x,y)}=\log{2^n}= O(n)$
follows directly.

% recording ~20:20
161 162
\paragraph{Example: \disjoint}

163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184
%\sunote{Didn't we define \disjoint in the last lecture notes?}
%\ronote{In response, we did define \disjoint, but in in lecture 1
%        we did not reason about the definition with as much detail.}
%
%We define $x$ and $y$ to be a vector of bits
%which define set membership.
%
%\begin{align*}
%            & x,y \in [0,1]^n \\
%\text{and } & x_i \Leftrightarrow i \in S_x \\
%            & y_i \Leftrightarrow i \in S_y
%\end{align*}
%
%the function $\disjoint(x,y)$ is defined as follows
%
%\begin{equation*}
%\disjoint(x,y) = \left\{
%  \begin{array}{l l}
%    1 & \quad \text{if $(x,y)$ are disjoint: } \left\{ \forall i, x_i \land y_i = 0 \right\} \\
%    0 & \quad \text{otherwise}
%  \end{array} \right.
%\end{equation*}
185 186 187 188 189 190 191 192 193 194 195 196


\begin{marginfigure}
\begin{tabular}{l l | l l l l}
    &     & $0$ & $0$ & $1$ & $1$ \\
    &     & $0$ & $1$ & $0$ & $1$ \\ \hline
$0$ & $0$ & $1$ & $1$ & $1$ & $1$ \\
$0$ & $1$ & $1$ & $0$ & $1$ & $1$ \\
$1$ & $0$ & $1$ & $1$ & $0$ & $0$ \\
$1$ & $1$ & $1$ & $0$ & $0$ & $0$ \\   
\end{tabular}
\\ \vspace{1em}
197
\caption{Matrix for $DISJ(x,y)$ when $n=4$ showing which
198
combinations will result in a $1$ or
199
a $0$.}
200 201 202 203 204 205 206
\end{marginfigure}

Let us observe one of the items in the
fooling set using our example.  Using the 
pair $(x_1, y_1) = (01, 10)$ and $(x_2, y_2) = (10, 01)$
we can see this is part of the fooling set.  This set
is interesting because $(x_1,y_1) = (\overline{x_2}, \overline{y_2})$.
207
In fact, the fooling st for $\disjoint(x,y)$ are the bit patterns with the bits flipped;
208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228
it is the set of all $A$ and $\overline{A}$.

% recording ~33:20

The fooling set $S = \{A, \overline{A}\}$.  Let us look at the
following properties.

\begin{align*}
 (A, \overline{A}) &= 1 \\
 (B, \overline{B}) &= 1 \\
 (A, \overline{B}) &= 1~\text{if}~B \supseteq A \\
 (\overline{A}, B) &= 1~\text{if}~A \supseteq B
\end{align*}

For this to not be a fooling set the bottom two
properties must be true.  Since this happens when
$B \supseteq A$ and $A \supseteq B$, it only happens
when $A=B$.

There can be $2^n$ combinations of elements in
the fooling set, so $|S| = 2^n$.  The complexity
229
of $\determin{\disjoint(x,y)} = \log 2^n = O(n)$
230 231 232 233 234 235 236 237 238 239

\section{Generalizing Fooling Set Argument}

\begin{proposition}
Let $\mu$ be a probability distribution of $X \times Y$.  If
any monochromatic rectangle R has measure $\mu \le t$\footnote{$t<1$},
then $\determin{f} \ge \log_2{\frac{1}{t}}$
\end{proposition}


240
For example, given a fooling set $S$ for a function $f$, let us define
241 242 243 244 245 246 247 248 249 250

\begin{equation*}
 \mu = \left\{ 
  \begin{array}{l l}
    \frac{1}{|S|} & \quad \text{for $(x,y) \in S$} \\
    0 & \quad \text{otherwise}
  \end{array} \right.
\end{equation*}

Each monochromatic rectangle can have at most $1$ element of the
251 252 253
fooling set, the measure of any monochromatic rectangle is $1/|S|$.
Thus this generalized the method based on fooling sets.
set.
254

255
\section{Rank based lower bound}
256 257 258 259

Let us define a matrix

\begin{equation*}
260
M_f = \{m_{ij} = f(x_i, y_i) | x_i \in X, y_i \in Y \}
261 262 263 264 265 266
\end{equation*}

\begin{lemma}
$\determin{f} \geq \log{\text{rank} (M_f)}$
\end{lemma}

267 268
\begin{proof}
  For a leaf, let us define
269 270

\begin{equation*}
271 272 273 274 275
  \ell : M_{\ell} = \left\{
    \begin{array}{l l}
      1 & \text{if $(x,y) \in R_{\ell}$} \\
      0 & \text{otherwise}
    \end{array} \right.
276 277
\end{equation*}

278 279
$\ell$ is the set of all leaves where the label is $1$.  The matrix $M_{\ell}$
is an indicator matrix for a leaf.
280 281

\begin{equation*}
282
  M_f = \sum_{\ell} M_{\ell}
283 284
\end{equation*}

285
Each $M_{\ell}$ is an all $1$'s matrix, so by the properties of rank.
286 287

\begin{equation*}
288
  \forall \ell, \text{rank}(M_{\ell}) = 1
289 290
\end{equation*}

291
If we have a collection of matrices $M_1 \ldots M_k$, then
292 293

\begin{equation*}
294
  \text{rank}\left( \sum_{i=1}^k M_i \right) \le \sum_{i=1}^k \text{rank} \left( M_i \right)
295 296
\end{equation*}

297 298
From this we can derive the rank of $M_f$ because we know the rank of each of
the matrices $M_{\ell}$.
299 300

\begin{equation*}
301
  \text{rank}\left( M_f \right) \le |L|
302
\end{equation*}
303
\end{proof}
304 305

These tools can be helpful for us to reason about the communication
306
complexity of a function using only algebraic tools rather
307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353
then reasoning about a problem combinatorially.

\paragraph{Inner product using rank}

We will define the function $IP(x,y)$ as

\begin{equation*}
IP(x,y) : x \bullet y~\text{over GF($2$)}
\end{equation*}

This problem is very tricky to solve using the fooling
set, as was mentioned before.  Using the rank argument
makes reasoning about $IP(x,y)$ must more easy.

The matrix for the this function is defined as

\begin{equation*}
M_{IP_{i,j}} = x_i \bullet y_j
\end{equation*}

We define the matrix $N=M_{IP}^2$.  More explicitly $N$ is
defined as

\begin{equation*}
N(y, y') = \sum_Z\left(y \bullet z \right) \left(z \bullet y'\right)
\end{equation*}

\begin{marginfigure}
$
\overbrace{
\begin{bmatrix}
0          & \rightarrow &        &    \\
\downarrow & 2^{n-1}     &        &  \\
           &             & \ddots &  \\
           &             &        & 2^{n-n} \\
\end{bmatrix}
}^{2^n}
$
\end{marginfigure}

We will be looking at the off diagonal of the matrix.
Lets say we have $y$ and $y'$ which have $r$ bits in common.
We need to make sure $z$ has $1$'s in all the $r$ bits.  The
rest we do not care about.  We are choosing some subset of the
$r$ bits to be fixed to $1$, the rest we can pick to be anything
else.  Doing this results in $2^n - 2^{n-r}$

354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378
% \sunote{See the note that I provided in the discussion group and insert it here}
The statement that the rank of the IP matrix over GF($2$)$=2^n$ is
not true.  A proof of this can be found in Sherstov's
notes\footnote{http://www.cs.ucla.edu/~sherstov/teaching2012-winter/docs/lecture03.pdf},
which we will briefly discuss here.

The first observation is that the rank argument works over any field.  So
we can choose the field we wish to evaluate matrix rank over.  In particular,
the rank over the reals is larger than the rank over any other field.

Recall that we would like to show that the inner product has deterministic
communication complexity $n$ via the rank method.  So we need to show that
the rank of the induced matrix (where $M_{ij}=<\!\!x_i,y_j\!\!>$) is large:
remember that IP is a function from $n$ bit string to $\{0, 1\}$.

Firstly, consider the auxiliary matrix $M'=2M-1$ (where $1$ is the all ons matrix).
All this does is change $0$ to $-1$ and $1$ to $1$, which is more convenient
to work with.  It is a nonsingular transformation, so $\text{rank}(M) \ge \text{rank}(M')-1$.

Now it is easy to see that $M'_{\text{IP}}$ on one-bit strings is the Hadamard
matrix\footnote{$ \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$} and the IP matrix for $n$ bit strings is merely the $n$-th order
version of this (or the $n$th tensor power of this matrix).  But this matrix
has full rank: in particular its rank is $2^n$.  Therefor the rank of the IP matrix
is at least $2^n-1$.

379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448

%recording ~1:00:00
\section{Randomized Algorithms}

Algorithms employing randomness make communication complexity
much more interesting and useful.

First question we need to ask before we study randomness in relationship
to communication complexity is who has the randomness?  Alice, Bob, or both?
For now, lets assume Alice and Bob each have their own \emph{private} source
of randomness, which will be indicated as $r_A$ and $r_B$ for Alice's and Bob's
random bits source respectively.  The source of the random bits ($r_A$ and $r_B$)
are only known by their owner.  If the randomness is to be shared, a communication
penalty will have to be paid.

\begin{marginfigure}
\centering
\includegraphics{figs/random_AliceBob}
\end{marginfigure}

When using randomness, each element in the protocol tree will
now include the random bits.  So each of Alice's nodes will
consider the triple $(x, \Pi, r_A)$, where $x$ is Alice's
private data, $\Pi$ is the knowledge the location and previous
information communicated, and $r_A$ are the private random
bits for Alice.  Randomness is over the choice of bits not
over the choice of inputs.

Using the notion of randomness, we can define different notions
for what the protocol is doing.  The following are the different
errors a randomized protocol can have:

\begin{description}
\item[zero error]

\begin{equation*}
Pr\left( P(x,y) = f(x,y) \right) = 1
\end{equation*}

\item[$\epsilon$ error] or two-sided error

\begin{equation*}
Pr\left( P(x,y) = f(x,y) \right) \ge 1 - \epsilon
\end{equation*}

\item[$1$ sided error]

\begin{align*}
Pr(P(x,y) = 0 | f(x,y) = 0 ) &= 1 \\
Pr(P(x,y) = 1 | f(x,y) = 1) &= 1 - \epsilon
\end{align*}
\end{description}

% recording ~1:05:00
The worst case running time for a random algorithm is 
the maximum time over all possible input and internal 
random bits.  The average case is the number of bits
which are expected to be communicated on average.



\begin{definition}
The complexity measures for each of the randomized protocols  listed
above.

\begin{itemize}
\item for zero error, $R_0(f)$ is the minimum average number of bits used for
 computing $f$ with $0$ error.

\item for $\epsilon$ error for $0 < \epsilon < 1/2$ (because $\epsilon$
449
 is two sided), $R_{\epsilon}$  is the \emph{minimum worst case} number 
450 451 452 453 454 455 456 457 458 459 460 461
 of bits for a $\epsilon$-error protocol.  We denote $R(f) = R_{1/3}(f)$.
 
\item for $1$ sided error for $0 < \epsilon < 1$, $R_{\epsilon}^1(f)$ is the minimum
worst case number of bits for a one sided error.  We denote $R^1(f) = R_{1/2}^1(f)$.
\end{itemize}
\end{definition}

% recording 1:09:00
\paragraph{An example} using equality with randomization.

We define $\equ(x,y) = 1$ if $x = y$.  Last week in lecture 1 we showed
 $\determin{\equ} = n+1$.  Using randomized algorithms we will show
462
 $\randR{\equ} = O(\log n)$.  This is exponentially better. 
463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
 
The trick is to think of the input as polynomials rather than
a sequence of bits.

We define the input for Alice and Bob to be a bit string $A$ and $B$
respectively.

\begin{align*}
A &: a_{n-1} \ldots a_0 \\
B &: b_{n-1} \ldots b_0
\end{align*}

We define the polynomials over $GF(p)$ (where $n^2 < p < 2n^2$) to be

\begin{align*}
A(x) &= \sum a_i x^i \\
B(x) &= \sum b_i y^i
\end{align*}

482 483
The randomized protocol is as follows.  Alice chooses $r \in GF(p)$ uniformly at
random.
484 485 486 487
Alice sends $r$ and $A(r)$ to Bob.  Bob checks if $B(r) = A(r)$.  If 
they are true, Bob declares that they are equal.  If Bob notices this
is not true, he declares they are not equal.

488
This works because polynomials can only agree at a small  number
489 490 491 492 493 494 495 496 497
 of locations without being equivalent.  Two degree-$n$ polynomials
 can only intersect at a maximum of $n$ points unless the polynomials
 are the same\footnote{This is trivial to prove using the fundamental theorem of algebra}.

\begin{marginfigure}
\centering
\includegraphics{figs/polynomial}
\end{marginfigure}

498
The size of $GF(p)$ is  $\Theta(n^2)$, as described above.  Using this information
499 500 501 502 503 504 505
we can calculate the following probability

\begin{equation*}
Pr(A(r) = B(r) | A \neq B) = \frac{n}{|GF(p)|} \sim \frac{1}{n}
\end{equation*}

How much communication is needed?  Alice must send $A(r)$, which
506
takes a single bit and $r$ which is drawn from a set of size $n^2$, so it will take
507 508 509 510 511 512 513 514 515 516 517 518 519
$2 \log n$ bits.  Bob must return the answer of if $A=B$, taking one
bit.  The total communication complexity is

\begin{equation*}
2\log n + 2 = O(\log n)
\end{equation*}

%\newpage

%\bibliographystyle{plain}
%\bibliography{L2}

\end{document}