\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb, bbm}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage[colorlinks = true]{hyperref}
\newcommand{\1}{\mathbbm{1}}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\DeclareMathOperator{\E}{\mathop{\mathbb{E}}}
\newcommand{\x}{\times}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}
\renewcommand{\bar}{\overline}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\eps}{\varepsilon}
\newcommand{\DTIME}{\textbf{DTIME}}
\renewcommand{\P}{\textbf{P}}
\newcommand{\SPACE}{\textbf{SPACE}}
\begin{document}
\input{preamble.tex}
\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\handout{CS 229r Information Theory in Computer Science}{April 16, 2019}{Instructor:
Madhu Sudan}{Scribe: Juspreet Singh Sandhu}{Lecture 21}
\section{Overview}
We define the (dynamic) Data-Structure model we wish to analyze, and prove a (weak) version of the prefix-sum lower bound. The references for the lecture are:
\begin{itemize}
\item \href{https://dl.acm.org/citation.cfm?id=73040}{Fredman \& Saks, '89} - The majority of the proof in this lecture gives an analysis that proves a weaker version of Theorem-3 in this paper (for the \textit{Partial sums} problem).
\item \href{https://www.youtube.com/watch?v=L8kSOdNZXSA}{Kasper Green Larsen, SITOC 2018, Part-1}, \href{https://www.youtube.com/watch?v=WgYLriUE7sA}{Kasper Green Larsen, SITOC 2018, Part-2}
\item \href{https://dl.acm.org/citation.cfm?id=149682}{Patrascu \& Demane, 2009}
\end{itemize}
\section{Dynamic Data-Structures \& Cell-Probe Model}
We lay down an (informal) definition of a dynamic Data-Structure, followed by the set of operations we wish to support. Then, we define the data-structure problem in its most abstract sense and end with a description of the Cell-Probe model as a concrete model to asses and measure the complexity of queries and prove lower bounds about them.
\subsection{Dynamic Data-Structures}
Informally, (dynamic) Data-Structures are objects that maintain data under dynamic updates; answer queries while using "small" amount of space, and process updates (and queries) efficiently. \\
Usually the operations we wish to support are:
\begin{itemize}
\item Update operations: \textit{Insert(i, S)}, \textit{Delete(i, S)}
\item Query operation: \textit{Query(i)}
\end{itemize}
To that end, we define our Data-Structure problem in its most abstract sense as:
\begin{defn}[Data-Structure Problem]
Given a sequence of query and update operations $\sigma_1,..,\sigma_m$, compute \textbf{Query($\sigma_1,..,\sigma_{m-1}; \sigma_m$)} efficiently.
\end{defn}
The computation of the query function above may be seen as computing the state that the data-structure should be in as a function of its present state $s(\sigma_{m-1})$ and the last received query $\sigma_m$. We wish to find lower bounds (space and time) on the computation of this query function for different problems.
\subsection{Cell-Probe Model}
The Cell-Probe model was proposed by \href{https://dl.acm.org/citation.cfm?id=322274}{[Yao, '79]} as a way to measure the time complexity of (dynamic) Data-Structures where the only cost payed is the total number of memory accesses.
\renewcommand{\arraystretch}{1.5}
\begin{center}
\[
\begin{array}{|r|r|l|l||} \hline
y_1 & y_2 & .... & y_s \\ \hline
\end{array}
\]
\end{center}
There are a total of $s$-cells in the array, and every cell holds a number $y_i \in \{-2^w, 2^w\}$, which stores the data pertaining to location $i$ and a pointer to the next cell $i + 1$. Denote by $l$ the length of a query $\sigma_i$. Then, we enforce that $w > l$ and $w > \log_2(s)$ (so that we can have pointers to any arbitrary cell). \\
It is important to note that every query $\sigma_i$ will lead to a set of accesses (read/write): $i_1 \rightarrow i_2 \rightarrow ... \rightarrow i_t$. These accesses are allowed to be \textbf{adaptive}:
\begin{defn}[Cell-Probe Adaptive Accesses]
$\forall \sigma_i$, the set of accesses $i_1 \rightarrow .. \rightarrow i_t$ are computed as: $i_k = g(i_{< k}; \sigma_i)$, $\forall k \in [t]$.
\end{defn}
\section{Examples \& Array Prefix-Sum problem}
Having defined our Data-Structure problem and the Cell-Probe model via which we will establish lower bounds on our query function, we state a few examples of problems for which we wish to establish lower bounds.
\subsection{Set Membership}
\begin{itemize}
\item \textit{Given}: A set $S \subseteq[U] = \{-2^l, .., 2^l\}$, such that, $|S| \leq n$
\item Query/Update operations:
\begin{itemize}
\item \textit{Insert(i, S)} $\rightarrow S \leftarrow S \cup \{i\}$
\item \textit{Delete(i, S)} $\rightarrow S \leftarrow S - \{i\}$
\item \textit{Query(i, S)} $\rightarrow \mathbbm{1}_{i \in S}$
\end{itemize}
\end{itemize}
We can solve this using a Search tree with $O(n)$ Space Complexity and $O(\log_2(n))$ Time Complexity (simply use a balanced tree with the right subtree being larger than the node, and the left subtree being smaller than the node). We can also use a Hash-Function based approach that has $O(n)$ Space Complexity, and $O(1)$ Time Complexity (Armortized).
\subsection{Partial Match Retrieval}
\begin{itemize}
\item \textit{Given}: A set $S \subseteq[U] = \{0, 1\}^l$, such that, $|S| \leq n$
\item Query/Update operations:
\begin{itemize}
\item \textit{Insert(i, S)} $\rightarrow S \leftarrow S \cup \{i\}$
\item \textit{Delete(i, S)} $\rightarrow S \leftarrow S - \{i\}$
\item \textit{Query(i, S)}, $i \in \{0,1,* \}^l$:
\begin{itemize}
\item 1, if $\exists y \in S$, st, $\forall i$ with $x_i \in \{0,1\}$, $x_i = y_i$
\item 0, otherwise
\end{itemize}
\end{itemize}
\end{itemize}
It turns out that outside of the trivial solution which requires $O(n)$ Space Complexity and Time Complexity (because of the Query function), getting a better solution is an open question: \\
\textbf{\textit{Open Problem}}: \textit{Does there exist a solution for Partial Match retrieval that requires $O(poly(n))$ Space Complexity and $\Tilde{O}(\log_2(n), l)$} Time Complexity ?
\subsection{Array Prefix-Sum}
\begin{itemize}
\item \textit{Given/Goal}: Maintain an array $A$ = $A[0],..,A[n-1]$
\item Query/Update operations:
\begin{itemize}
\item \textit{Update(i, $\Delta$}): $A[i] \leftarrow \Delta$
\item \textit{Query(i)}: return $\sum_{j \leq i} A[j]$
\end{itemize}
\end{itemize}
This problem presents a few solutions, all of which (as we shall see in Section-4) respect the \href{https://dl.acm.org/citation.cfm?id=73040}{[Fredman-Saks, '89]} lower bound. A slight modification is that the paper defines the \textit{Update} operation as addition as opposed to an over-riding operation. However, we assume that an update essentially over-rides the value at that position. We define $t_U$ to be the Time Complexity of the update operations, and $t_Q$ to be the Time Complexity of the query operations.
\begin{itemize}
\item $[$Array$]$ $t_U$ = $O(1)$, $t_Q$ = $O(n)$
\item $[$Binary Tree$]$ $t_U$ = $O(\log_2(n))$, $t_Q$ = $O(\log_2(n))$
\end{itemize}
\section{Array Prefix-Sum lower bound \& Proof}
We begin by stating the strong theorem (that we shall not prove), followed by the weaker version (that we shall prove).
\begin{theorem}[Strong Prefix-Sum Lower Bound]
For Array Prefix-Sum queries, $t_U$ + $t_Q$ $\geq$ $\frac{\log_2(n)}{\log_2(\frac{w}{l})}$
\end{theorem}
\begin{theorem}[Weak Prefix-Sum Lower Bound]
For Array-Prefix Sum queries, $t_Q$ $\geq$ $\frac{\log_2(n)}{\log_2(\frac{t_U\cdot w}{l})}$
\end{theorem}
\textbf{Proof}: We first sketch an overview of how the proof will proceed, and then provide the details by splitting into 2 parts:
\begin{itemize}
\item \textit{FREDMAN-SAKS Chronogram}: Constructing a chronogram to partition and initialize $A[0],..,A[n-1]$ by using over-writes to geometrically decreasing buckets of the array (iterated over a finite number of epochs), and then choosing a query $q = \sigma_i \sim_{r} [n]$.
\item \textit{Lower bound $CC_{\epsilon}$(Compute($A[0]..A[n-1]$)}: Partitioning the epochs $U_1,..,U_j$ in the chronogram into 3 buckets $A, B, C$, where Alice gets buckets $A, B, C$, Bob gets buckets $A, C$, and constructing a one-way communication protocol in which Alice sends Bob the minimal number of bits possible so that Bob can compute the correct values of the original array (in the bucket $B$). Here, $j \approx \frac{\log_2(n)}{\log_2(\beta)}$ = \# of epochs, where $\beta \geq t_U$.
\end{itemize}
To make our ultimate claim, we will first define 2 sets and state a helper lemma, the claim to which will imply our \textbf{Theorem-4} (with a little more analysis). \\
\subsection{Fredman-Saks Chronogram}
Let the number of epochs $j \approx \frac{\log_2(n)}{\log_2(\beta)}$ and $\beta \geq t_U$. \\
Construct the $j$ epochs in the following manner: \\
\begin{itemize}
\item $U_0$: $A[i] \leftarrow \Delta_{i, 1}$, $\forall i \in \{0,..,(n-1)\}$
\item $U_1$: $A[\beta\cdot i] \leftarrow \Delta_{i, 2}$, $\forall i \in \{0,..,(\frac{n}{\beta}-1)\}$
\item $U_1$: $A[\beta\cdot i] \leftarrow \Delta_{i, 3}$, $\forall i \in \{0,..,(\frac{n}{\beta^2}-1)\}$
\item ...
\item $U_1$: $A[\beta\cdot i] \leftarrow \Delta_{i, j}$, $\forall i \in \{0,..,(\frac{n}{\beta^j}-1)\}$
\end{itemize}
We then select the query $q \sim_r [n]$. Assume that our cell-probe is now $j$-colored, such that we color every cell that was updated in a particular epoch with a color. Note that our epochs are geometrically decreasing in size, but we will rewrite certain cells multiple times, and therefore, we will be interested in the color assigned to a particular cell $y_i$ in the last epoch to update it. We now introduce a few elementary definitions:
\begin{defn}
$C(i)$ = $\{t$ $|$ Color of $y_t = i\}$
\end{defn}
\begin{defn}
$p_(q)$ = Set of cells probed on query $q$
\end{defn}
\subsection{One-way Communication analysis}
In order to prove our main theorem, it suffices to prove the following helper lemma: \\
\begin{lemma}
$\forall i \in [j], \displaystyle \mathop{E}_{U_1,..,U_m,q}[C(i) \cap p(q)] = \Omega(1)$, provided $\beta \geq \frac{t_U\cdot w}{l\cdot \epsilon}$
\end{lemma}
The proof for this lemma follows from an analysis of the one-way communication protocol, based on choosing $A = U_1,..,U_{i-1}$, $B = U_i$ and $C = U_{i+1},..,U_{j}$. We let the status of the array at $U_{i-1} = D$ and $U_i = D^{'}$. Initially, Bob sets $D = D^{'}$, but then runs the query function $q$ (some fixed number of times: $O(\frac{1}{\epsilon^2})$ so as to obtain a fixed error $\epsilon$) and updates the cells in $U_i$. \\
Bob is allowed to make errors, but since Alice knows $A,B,C$, she can run the same query $q$ and predict for what $j \in U_i$ will Bob make an error. This is \textit{precisely} the set of bits: $A_{j_1},..,A_{j_m} \in U_i$ she sends to Bob (in addition to the information about the updates in $C$) so that he can correctly construct $B$. Since Bob knows $A$ and $C$, and the query function is adaptive, with Alice's correcting bits he can construct $B$. \\
The probability that Bob makes an error is: $Pr[error] \leq 2\epsilon\frac{n}{\beta^i}$ \\
Note that as $B$ is chosen to be $U_i$ independently, it has maximum entropy even when conditioned on $A$ and $C$. So: \\
$H(B$ $|$ $A, C)$ = $H(B)$ = $|U_i|\cdot l$ = $\frac{nl}{\beta^i}$ \\
The last remaining part of the puzzle is the number of bits that Alice sends to Bob, i.e., the message length: \\
$|m| = |C|\cdot t_U(w + O(\log_2(s))$ + correcting bits \\
Here, the updates are the scaled by the size of each word that can be stored in the cell-probe, as well as some auxiliary bits for pointing into the correct indices. Note that, as $\beta > 1$, $|U_i| \geq \displaystyle \sum_{p=i+1}^{j} U_p$. Given that the length of the query is $l$, the total message length is the information about the updates plus the set of corrections: \\
$|m| = |C|\cdot t_U(w + O(\log_2(s)) + 2\epsilon\frac{n}{\beta^i}\cdot l$ = $O(\frac{n\cdot t_U \cdot W}{\beta^{i + 1}}) + 2\epsilon\frac{n}{\beta^i}\cdot l$ \\
By choosing $ \beta \geq \frac{t_U\cdot W}{(1 - 2\epsilon)l}$, we obtain $\displaystyle \mathop{E}_{U_1,..,U_m,q}[C(i) \cap p(q)] \geq \epsilon$. \\
Since the expectation is over positive random variables, we see that this expectation is $\Omega(1)$, $\forall i \in [j]$. \\ \\
To complete the proof, we use our inequality over $\beta$ to obtain that: \\
$t_Q \geq \frac{\log_2(n)}{\log_2(\beta)}$ \\
By making the $\epsilon$ sufficiently small, we can substitute $\beta \approx \frac{t_U\cdot w}{l}$. This implies that: $t_Q \geq \frac{\log_2(n)}{\log_2(\frac{t_U\cdot w}{l})}$ \\
This proves the statement in \textbf{Theorem-4}. \\
\textbf{QED}
\end{document}