
\documentclass[10pt]{article}
\newtheorem{define}{Definition}
\newcommand{\D}{\mathbf{D}}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\usepackage[ruled,vlined,linesnumbered]{algorithm2e}
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{automata,positioning}
\usetikzlibrary{decorations.pathmorphing,shapes}
\usepackage{amssymb}



\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{1}{February 6, 2019}{Ronitt Rubinfeld}{Sandeep Silwal}

%%%% body goes in here %%%%


\section{Outline}
The following topics were covered in class:
\begin{itemize}
\item Overview of the course.
\item Diameter of a point set.
\item Estimating the number of connected components of a graph.
\end{itemize}

\section{Overview of the course}
The high-level goal of sublinear time algorithms is to answer questions without reading or processing the entire input. Therefore, we have to make a compromise which usually means introducing an error parameter along with a probability that your approximation holds. Hence, algorithms in this field are usually randomized. In addition to randomized algorithms, the field of sublinear time algorithms also intersects with approximation algorithms, parallel algorithms, distributed algorithms, statistics and many other fields. 

The complexity of algorithms is measured in terms of the number of queries that we request from the input data, such as querying an adjacency matrix or asking for a sample from a distribution. This general framework can be applied to a variety of different types of inputs. Some examples of inputs and the properties of these inputs that we can ask questions about are shown in Table \ref{table:topics}. We will cover most of the things in Table \ref{table:topics} in due time.

\begin{table}[!htbp]
\renewcommand*{\arraystretch}{1.4}
\begin{tabular}{|c|c|} 
\hline
\textbf{Type of input} & \textbf{Properties that we can ask questions about}                                  \\ \hline
Graphs                 & Diameter, $\#$ of connected components, MST, bipartiteness, clusterability, $\cdots$ \\ \hline
Functions              & Monotonicity, convexity, linearity, juntas, $\cdots$                                 \\ \hline
Distributions          & Uniformity, independence, entropy, monotonicity, $\cdots$                            \\ \hline
\end{tabular}
\caption{\label{table:topics} Topics that we might cover in the course.}
\end{table}

Let's begin by discussion the only non randomized algorithm in this course.

\section{Diameter of a point set}

Consider $m$ points in some metric space whose pairwise distances are given in the matrix $\D$. That is, $\D_{ij}$ is the distance between point $i$ and point $j$. Since we are in a metric space, we assume the following things about $\D$:
\begin{itemize}
\item $\D$ is symmetric: $\D_{ij} = \D_{ji}$ for all $i,j$.
\item $\D$ satisfies the triangle inequality:
$\D_{ij} \le \D_{ik} + \D_{kj}$ for all $i,j,k. $
\end{itemize}
Our goal is to find the diameter of this point set, that is, we want to find the maximum entry in the matrix $\D$. Moreover, we want to find the points that achieve this diameter. We won't be able to do this exactly but we will instead give a \emph{2-approximation} by using the fact that our points lie in a metric space. Our algorithm is the following.
\begin{algorithm}[!h]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{$m$ points in a metric space, matrix $\D$ of all the pairwise distances.}
  \Output{Points $k, \ell$ and distance $\D_{k, \ell}$.}
    Pick $k$ arbitrarily from $\{1, \cdots, m\}$ \;
    Pick $\ell$ that maximizes $\D_{k, \ell}$\;
    Return $k, \ell, \D_{k, \ell}$
    \caption{$\textbf{Diameter-Estimator}$}
    \label{alg:diameter-estimator}
\end{algorithm}

\begin{theorem} \label{thm:diam}
$\textbf{Diameter-Estimator}$ returns a $2$-approximation to the actual diameter.
\end{theorem}

\begin{proof}
Consider the points $k$ and $\ell$ outputted by $\textbf{Diameter-Estimator}$. Suppose that the actual diameter is achieved by points $i$ and $j$. Then by the triangle inequality, we have 
$$ \D_{ij} \le \D_{ik} + \D_{kj} = \D_{ki} + \D_{kj} \le 2 \D_{k,\ell}, $$
as desired.
\end{proof}

\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[font=\sffamily]

        % Setup the style for the states
        \tikzset{node style/.style={state, 
                                    minimum size=0.5cm,
                                    line width=0.5mm,
                                    fill=gray!10!white}}

        % Draw the states
        \node[node style] at (-3, 0)         (k)     {\Large $k$};
        \node[node style] at (3, 0)     (u)     {\Large $\ell$};
        \node[node style] at (-2, -2)     (i)     {\Large $i$};
       \node[node style] at (2, 2.3)     (j)     {\Large $j$};
        \draw[thick, line width=0.5mm,] (u) -- (k);
        \draw[thick, line width=0.5mm,] (i) -- (j);
        \draw[thick, line width=0.5mm, dashed] (i) -- (k);
      \draw[thick, line width=0.5mm, dashed] (j) -- (k);
    \end{tikzpicture}
    \caption{\label{fig:diameter}We use the triangle inequality on the points $k, i, j$ in the proof of Theorem \ref{thm:diam}.}
\end{figure}

Note that the size of the input is $ n = m^2$ since $\D$ has $m^2$ entries. Furthermore, the query complexity of $\textbf{Diameter-Estimator}$ is $O(m)$ since we examine one row of $\D$. Therefore, the complexity of our algorithm is $O(\sqrt{n})$, which is sublinear in the input size. 

\section{Number of connected components}
We now move onto our second topic which is to estimate the number of connected components of a graph. Given an input $G = (V,E)$ with $|V| = n$ and an error parameter $\epsilon > 0$, our goal is to output an estimate for $c$, the number of connected components of $G$. Our complexity will be measured in terms of the number of queries that we make to the graph.

We will give an algorithm that outputs an estimate $\widetilde{c}$, and we will show that we get an additive error of at most $\epsilon n$, that is, $|c - \widetilde{c}| \le \epsilon n$ (with probability at least $\frac{3}4$).  To motivate the algorithm, we first introduce a new notation. 
\begin{definition}
For $v \in V$, define $n_v$ to be the number of nodes in the connected component of $v$.
\end{definition}

The key observation is if $A \subseteq V$ is a connected component, we have $\sum_{v \in A} \frac{1}{n_v} = 1$. Thus,
\begin{equation} \label{eq:comp}
\sum_{v \in V} \frac{1}{n_v} =  \# \textup{ of connected components} = c.
\end{equation}
Therefore, we can use Eq.\@ (\ref{eq:comp}) to calculate $c$. Our strategy is to first get a good approximation for $n_v$ for a fixed $v$. The guiding principle behind this estimate will be that if $n_v$ is small, the connected component that $v$ belongs to is small and therefore we will incur small query complexity to just search over the entire connected component of $v$. 

On the other hand, if $n_v$ is large, we know $\frac{1}{n_v}$ is small so we will incur a small error by approximating $n_v$. We then approximate $\sum_{v \in V} \frac{1}{n_v}$ using our approximation for $n_v$. Our guiding principle here will be that we can sample vertices at random to approximate the average value of $\frac{1}{n_v}$. Towards this goal, we make the following definition.
\begin{definition}
$\widehat{n}_v = \min\{ n_v, 2/\epsilon \}.$
\end{definition}
Again, the intuition behind this definition is that we want to separate the cases that $n_v$ is small versus large. We now show that this estimate incurs us a very small loss in Eq.\@ (\ref{eq:comp}).
\begin{lemma} \label{lem:estimate}
The following estimate holds for all vertices $v \in V$:
$$\frac{1}{\hat{n}_v} - \frac{1}{n_v} \le \frac{\epsilon}2.$$
\end{lemma}
\begin{proof} 
If $n_v \le \frac{2}{\epsilon}$, we have $\widehat{n}_v = n_v$ so the claim immediately follows. Otherwise, 
$n_v > \frac{2}{\epsilon}$ and $\widehat{n}_v = \frac{2}{\epsilon}$ and 
 $$0 \le \frac{1}{n_v}  \le \frac{1}{\widehat{n}_v}  = \frac{\epsilon}2$$ so the conclusion also follows.
\end{proof}

We formalize our heuristics and present an algorithm to compute $\widehat{n}_v$.

\begin{algorithm}[!h]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G$, vertex $v$, $\epsilon$ }
  \Output{$\widehat{n}_v$.}
  Initialize Breadth-first search (BFS) from $v$ \;
  \While{$\#$ of unique visited nodes by BFS is $< \frac{2}{\epsilon}$}	
    { Continue BFS \;
    \If{ BFS finishes}
      {Return number of visited nodes and abort}  }
    Return $\frac{2}{\epsilon}$

    \caption{$\widehat{n}_v\textbf{-Calculator}$}
    \label{alg:compute-nhat}
\end{algorithm}

Note that the query complexity of this algorithm is $O(1/\epsilon^2)$. This is because we visit at most $O(1/\epsilon)$ unique vertices and for each of them, we visit at most $O(1/\epsilon)$ of their neighbors (some of the neighbors might be repeated, think of a clique of size $O(1/\epsilon)$).

We now proceed to estimate the \emph{sum} in Eq.\@ (\ref{eq:comp}). We first define a similar quantity  
\begin{equation} \label{eq:chat}
\hat{c} = \sum_{v \in V}\frac{1}{\widehat{n}_v}.
\end{equation}
From Lemma \ref{lem:estimate}, we know that computing $\hat{c}$ gives us a desirable approximation for $c$, the true number of connected components. However, simply estimating $\widehat{n}_v$ for each $v \in V$ is too costly (this is sublinear time algorithms after all) so we must do something clever. Fortunately, we don't have to be too clever since computing $\hat{c}$ is the same as computing the average value of $1/\widehat{n}_v$. This last task can be easily handled by standard concentration bounds. Therefore, our task is to now find an `good' approximation for $\hat{c}$, which will be denoted as $\tilde{c}$, and use Lemma \ref{lem:estimate} to argue that we also have a good estimate for $c$. 
\begin{algorithm}[!ht]
    \SetKwInOut{Input}{Input}
    \SetKwInOut{Output}{Output}
  \Input{Graph $G$,  $\epsilon$, $b$ }
  \Output{$\tilde{c}$.}
  $r \gets b/\epsilon^3$ \;
  Sample $r$ vertices $v_1, \cdots, v_r$ from $G$ uniformly with replacement \;
  Compute $\widehat{n}_{v_i}$ for all $1 \le i \le r$ using $\widehat{n}_v\textbf{-Calculator}$ \;
  Return $\tilde{c} = \frac{n}r \left( \sum_{i = 1}^r 1/\widehat{n}_{v_i} \right)$
    \caption{$\tilde{c}\textbf{-Calculator}$}
    \label{alg:compute-chat}
\end{algorithm}
We present an algorithm to calculate $\tilde{c}$ in Algorithm \ref{alg:compute-chat}. Note that from the discussion from Algorithm \ref{alg:compute-nhat}, the query complexity of Algorithm \ref{alg:compute-chat} is $O(1/\epsilon^5)$. We proceed to show that $\tilde{c}$ from Algorithm \ref{alg:compute-chat} is a `good' approximation to $\hat{c}$.

\begin{lemma} \label{lem:approxc}
Let $\tilde{c}$ be the output of Algorithm \ref{alg:compute-chat} (for some constant $b$ to be specified later). Then 
$$\mathbb{P}  [ | \hat{c}-\tilde{c}| \ge \epsilon n/2] \le \frac{1}4.$$
\end{lemma}
We need the following variant of Chernoff bounds to prove Lemma \ref{lem:approxc}.
\begin{theorem}[Chernoff]
Let $X_1, \cdots, X_r$ be i.i.d. random variables in the unit interval. Define \newline $S = \sum_{i=1}^r X_i$ and $p = \mathbb{E}[X_i]$. Then,
$$ \mathbb{P} \left [ \left | \frac{S}{r}-p \right | \ge \delta p \right ] \le \exp \left( - \Omega(r p \delta^2 ) \right ).$$
\end{theorem}
We now prove Lemma \ref{lem:approxc}.
\\

\begin{proof}
Consider the vertices $v_1, \cdots, v_r$ in Algorithm \ref{alg:compute-chat} that are sampled uniformly from $G$ and let $\tilde{c}$ be the output of Algorithm \ref{alg:compute-chat}. Recall Eq.\@ (\ref{eq:chat})
$$ \hat{c} = \sum_{v \in V}\frac{1}{\widehat{n}_v}.$$ We wish to upper bound $\mathbb{P}  [ | \hat{c}-\tilde{c}| \ge \epsilon n/2]$. Note that $\hat{c} \le n$ so
$$
\mathbb{P}  [ | \hat{c}-\tilde{c}| \ge \epsilon n/2] \le \mathbb{P}  [ | \hat{c}-\tilde{c}| \ge \epsilon \hat{c}/2]  = \mathbb{P}  \left[  \left | \frac{\hat{c}}n- \frac{\tilde{c}}n \right | \ge \frac{\epsilon \hat{c}}{2n} \right ].
$$
Now let $X_i = 1/\widehat{n}_{v_i}$. It follows that 
$$ \mathbb{E} [X_i] = \frac{1}n \sum_{i = 1}^r \frac{1}{\widehat{n}_{v_i}} = \frac{\hat{c}}n.$$ 
Furthermore,
$$ \frac{1}r \sum_{i=1}^r X_i = \frac{1}r  \sum_{i=1}^r \frac{1}{\widehat{n}_{v_i}} = \frac{\tilde{c}}n. $$ Now let $\delta = \frac{\epsilon}2$. The Chernoff bound gives us 
$$ \mathbb{P}  \left[  \left | \frac{\hat{c}}n- \frac{\tilde{c}}n \right | \ge \frac{\epsilon \hat{c}}{2n} \right ] \le \exp(- \Omega( \hat{c}/\epsilon n) ).  $$
Since $$\frac{\epsilon n} 2 \le \sum_{v \in V} \frac{1}{\widehat{n}_v} = \hat{c}$$ by definition, it follows that by picking a suitably large constant for $b$, we have 
$$\mathbb{P}  [ | \hat{c}-\tilde{c}| \ge \epsilon n/2] \le \frac{1}4,$$
as desired.
\end{proof}

We now combine Lemmas \ref{lem:estimate} and \ref{lem:approxc} to prove the main theorem of this section.\

\begin{theorem} \label{thm:main}
Let $c$ be the number of connected components of $G$ and let $\tilde{c}$ be the output of Algorithm \ref{alg:compute-chat}. Then, 
$$\mathbb{P}  [ | c-\tilde{c}| \le \epsilon n] \ge \frac{3}4.$$
\end{theorem}
\begin{proof}
By the triangle inequality,
$$ |c - \tilde{c}| \le | \hat{c} - c| + |\hat{c}-\tilde{c}|.$$
By Lemma \ref{lem:estimate}, 
$$| \hat{c} - c| = \sum_{v \in V}  \frac{1}{\hat{n}_v} - \frac{1}{n_v}  \le \frac{\epsilon n }2.$$ 
Furthermore, by Lemma \ref{lem:approxc}, $  | \hat{c}-\tilde{c}| \le \frac{\epsilon n}2 $
with probability at least $\frac{3}4$. Hence with probability at least $\frac{3}4,$ we have
$$ |c - \tilde{c}| \le \frac{\epsilon n}2 + \frac{\epsilon n}2 = \epsilon n,$$
as desired.
\end{proof}

Theorem \ref{thm:main} tells us that our estimate for the number of connected components is off by an additive factor of at most $\epsilon n$. Interestingly, our overall query complexity is $O(1/\epsilon^5)$ (which can be optimized slightly) which has no dependence on $n$.

\end{document}



