%---------change this every homework
% place your email id between the braces so that your homework has a name
\def\yourname{}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{Thu Jan 31, 2019}
\def\duelocation{In class}
\def\hnumber{1}
\def\prof{Huy Nguyen}
\def\course{\href{http://www.ccs.neu.edu/home/hlnguyen/cs7880/spring19/index.html}{cs7880 - algorithms - s'19}}
%-------------------------------------
\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage{subfig}
\usepackage{algpseudocode}
\usepackage{enumitem}
\usepackage{algorithm}
\usepackage{listings}
%\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{fullpage}
\usepackage{color}
\definecolor{mdb}{rgb}{0.3,0.02,0.02}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
%\pagestyle{myheadings}
\markboth{\yourname}{\yourname}
\thispagestyle{empty}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
\renewcommand{\thepage}{H\hnumber-\arabic{page}}
\noindent
\begin{center}
\vbox{
\hbox to \columnwidth {\sc{\course} --- nguyen \hfill}
\vspace{-2mm}
\hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
}
\end{center}
\vspace*{2mm}
}
\newcommand{\solution}[1]{\medskip\noindent{\color{cit}\textbf{Solution:} #1}}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{claim}{Claim}
\newcommand{\eps}{\epsilon}
\begin{document}
\handout
\begin{itemize}
\item The assignment is due on January 31 in class. Late assignments will not be accepted. Submit early and often.
\item You are permitted to study with friends and
discuss the problems; however, {\em you must write up you own
solutions, in your own words}. Do not submit anything you
cannot explain.
If you do collaborate with any of the other students on any
problem, please do list all your collaborators in your
submission for each problem.
\item Finding solutions to homework problems on the web, or by asking
students not enrolled in the class is strictly prohibited.
\item We require that all homework submissions are prepared in Latex. If you need to draw any diagrams,
however, you may draw them with your hand.
\end{itemize}
\begin{problem}{Approximate counter}\end{problem}
In class we analyzed an approximate counter that counts up to $n$ using $O(\log \log n)$ bits: initialize $X$ to $0$ and for every update, we increase $X$ with probability $2^{-X}$. By averaging many such estimators, we obtained a $1\pm\eps$ approximation with constant probability. Here we consider a variation of the algorithm. We still initialize the counter $X$ to $0$ but for each update, we increase $X$ with probability $1/(1+a)^X$. Note that our estimator for $n$ has to change from $2^X-1$ to something else and this is part of the problem.
{\em Question}: How small do we need to set $a$ so that our estimate $\hat{n}$ of $n$ satisfies $|n-\hat{n}| \le \eps n$ with probability at least $9/10$ when we return the output of only a single estimator instead of averaging many estimators as in class.
\begin{problem}Fast $\ell_2$ estimator\end{problem}
Recall the AMS sketch from class for estimating the $\ell_2$ norm of the input vector $x\in\mathbb{R}^n$: a random $m\times n$ matrix $\Pi$ with entries $\pm 1/\sqrt{m}$ is drawn for $m=O(1/\eps^2)$ and $\|x\|^2$ is estimated as $\|\Pi x\|^2$. Then with probability at least $2/3$, we have
\begin{equation}\label{l2-approx}
(1-\eps)\|x\|_2^2 \le \|\Pi x\|_2^2 \le (1+\eps)\|x\|_2^2
\end{equation}
The update time of this algorithm is $O(1/\eps^2)$ because when we add $\delta$ to coordinate $x_i$ we need to update every coordinate of $\Pi x$. An approach to improve the update time is to use sparser random matrix $\Pi$. Imagine picking $\Pi$ as follows: for each $i\in \{1,2,\ldots, n\}$ we pick a uniformly random number $h_i \in\{1,\ldots, m\}$. We then set $\Pi_{h_i,i}=\pm 1$ for each $i\in\{1,\ldots, n\}$ and all other entries of $\Pi$ are set to $0$. This $\Pi$ has the advantage that when we update coordinate $x_i$, we only need to change coordinate $h_i$ of $\Pi x$ and thus, the update time is constant. Show that this $\Pi$ still satisfies equation~(\ref{l2-approx}) with probability $2/3$ for $m=O(1/\eps^2)$.
\end{document}