\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\newcommand{\p}{\cclass{P}}
\newcommand{\np}{\cclass{NP}}
\newcommand{\pcp}{\cclass{PCP}}
\newcommand{\am}{\cclass{AM}}
\newcommand{\ma}{\cclass{MA}}
\newcommand{\qp}{\cclass{QuasiP}}
\newcommand{\etime}{\cclass{E}}
\newcommand{\exptime}{\cclass{EXP}}
\newcommand{\ph}{\cclass{PH}}
\newcommand{\cnp}{\cclass{coNP}}
\newcommand{\dtime}{\cclass{DTIME}}
\newcommand{\bpp}{\cclass{BPP}}
\newcommand{\bqp}{\cclass{BQP}}
\newcommand{\ntime}{\cclass{NTIME}}
\newcommand{\size}{\cclass{SIZE}}
\newcommand{\ppoly}{\cclass{P_{/poly}}}
\newcommand{\dspace}{\cclass{SPACE}}
\newcommand{\pspace}{\cclass{PSPACE}}
\newcommand{\bpl}{\cclass{BPL}}
\newcommand{\aco}{\cclass{AC^0}}
\newcommand{\calC}{\mathcal{C}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{question}{Question}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\vartriangle}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\of}{\overline{f}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\pmo}{\{\pm 1\}}
\newcommand{\tsat}{\mathsf{3SAT}}
\newcommand{\gni}{\mathsf{GNI}}
\newcommand{\replac}{\mathbin{\raisebox{.2ex}{
\hspace{-.4em}$\bigcirc$\hspace{-.75em}{\rm \tiny R}\hspace{.15em}}}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\title{COS 522 - Complexity - Final Take Home Exam}
%
%\author{Boaz Barak}
\begin{document}
%\maketitle
\begin{center}{\Large \textbf{COS 522 Complexity - Spring 2007 - Final Take Home Exam}}\end{center}
\begin{itemize}
\item Read these instructions carefully \emph{before} starting to work on
the exam. If any of them are not clear, please email me before you
start to work on the exam.
\item \textbf{Schedule:} You can work on this exam in a
period of $48$ hours of your choice between May
7$^{th}$ to \textbf{May 21$^{st}$ 10:00am}. You should
type up your exam (preferably using \LaTeX ) and email
it to me by May 21$^{st}$ 10:00 am. \emph{This is a
strict deadline}. You may submit the exam earlier. In
addition, please submit a hardcopy of the exam to my
mailbox.
\item \textbf{Restrictions , honor code:} You should work
on the exam alone. You can use your notes from the
class, the homework exercises and their solutions, the
textbook and the handouts I gave in class. You can also
use any personal summaries and notes of the material
that you prepare before starting to work on the exam.
\emph{You should not use any other material while
solving this exam}. You should write and sign the honor
pledge on the hardcopy of the submitted exam (the
pledge is ``I pledge my honor that I did not violate
the honor code during this exam and followed all
instructions'').
\item \textbf{Writing:} You should answer all questions
\emph{fully}, \emph{clearly} and \emph{precisely}. When describing
an algorithm or protocol, state clearly what are the inputs,
operation, outputs, and running time. When writing a proof, provide
clear statements of the theorem you are proving and any intermediate
lemmas or claims.
\item\textbf{Partial solutions:}
If there is a question you can not solve fully, but you can
solve a partial/relaxed version or a special case, then please state
clearly what is the special case that you can solve, and the
solution for this case. You will be given partial credit for such
solutions, as long as I feel that this special case captures a
significant part of the question's spirit.
\item\textbf{Quoting results:} You can quote without proof
standard mathematical tools
such as Chernoff bounds, and concepts from linear algebra (inner
product, eigenvalues etc.). However, you should quote the results
precisely, and give a reference to the place in the textbook
where the result is
stated.
%\item \textbf{Polynomial security:} Whenever in this exam we say that a primitive is \emph{secure}
%under some attack, we mean that it is $(T(n),\e(n))$ secure for
%$T(n)=n^{\omega(1)}$ and $\e(n)=n^{-\omega(1)}$, where $n$ is the
%key size/security parameter of the scheme . That is, any adversary
%that is implementable by polynomial-sized circuit, and attacks the
%primitive has probability less than $1/poly(n)$ of success (for
%every polynomial $poly(\cdot)$ and large enough $n$). The conditions
%of the attack and meaning of success are of course determined by
%particular security definition.
%
%
%\item \textbf{Assumptions:} You may assume as true any of the axioms/assumptions that
%were given in class: existence of one-way permutations, commitment
%schemes, pseudorandom generators, pseudorandom permutations,
%hardness of factoring random Blum integers, hardness of inverting
%the RSA permutation, decisional Diffie Hellman, existence of
%chosen-message (CMA) secure signature schemes, existence of
%collision-resistant hash functions, existence of chosen ciphertext
%(CCA) secure encryption schemes, and existence of secure oblivious
%transfer (OT) and private information retrieval (PIR) protocols.
%Whenever you use such an assumption, state it clearly and precisely.
%It is recommended that you review these assumptions and definitions
%before you start working on this test.
%
%\textbf{Note on the random oracle model:} You can use the random
%oracle model, but it is preferred that you avoid doing so if
%possible (you will get at least the majority of points for a valid
%solution in the random oracle model). If you use as a black-box a
%CCA secure encryption scheme this does not count as using the random
%oracle model (even though the only construction we saw for this in
%class used the random oracle model).
%
%
%\item\textbf{Quoting results:} You can quote without proof theorems that were proven in
%class. However, you should quote them precisely, and state the date
%and lecture number where the theorem was proven. You can also use
%the hardcore theorem of Goldreich and Levin, even though it was not
%fully proved in class. When solving a question, you can use the
%results of a previous question as given, even if you did not manage
%to solve it.
%
\item\textbf{Clarifications:}
I have made an effort to make the questions as clear and unambiguous
as possible. In case any clarifications are needed, I will try to be
always available by email. You can also email me with your number
and good times to call, and I will call you back. If you need me
more urgently, you can call me at my cell phone 917-674-6110 between
10am and 10pm eastern time. If there are any unresolved doubts,
please write your confusion as part of the answer and maybe you
will get partial credit.
\end{itemize}
\textbf{\Large Turn the page only when you are ready to start
working on the exam.}
\newpage
~
\begin{center} This exam has a total of $4$ questions,
each worth $25$ points, summing up to $100$ points.
\end{center}
\begin{question} Prove that if $G$ is an $(n,D,1-\e)$-graph and $G'$ is
a $(D,d,1-\e')$-graph then the (balanced) \emph{replacement
product} $G \replac G'$ of of $G$ and $G'$ (as defined in
Section 16.4.4) is an $(nD,2d,1-(\e\e')^4/100)$ graph. (This is
implied by Lemma~16.23 but there's actually a bug in the proof
of that lemma in the book, since it relied on an inaccurate
description of the adjacency matrix of the replacement
product.)
\end{question}
\begin{question} Prove Theorem~16.25: There exist constants $d \in \N$ and $\lambda<1$
such that there is a strongly explicit family of $d$ regular
$\lambda$-expander graphs $\{ G_N \}_{N\in\N}$. That is, for
every $N$, $G_N$ is an $(N,d,\lambda)$-graph and there is a
polynomial-time algorithm $A$ that on input $(N,u,i)$
(represented in binary) where $u \in [N]$ and $i\in[d]$,
outputs the index of the $i^{th}$ neighbor of $u$ in $G_N$. You
may use any lemma that has a full proof in the text and also
the result of the previous question. See footnote for
hint\footnote{\textbf{Hint:} \tiny First show how to teak the
construction of the text to obtain such a graph for every $N$
that is of the form $N=c^n$ for some constant $c$. Then, show
that you can use this to obtain a construction of graphs of
every size.}
\end{question}
\begin{question} Solve Exercise~16.9. That is, prove that if
$k\in\N$ and $X$ is a distribution over $\bits^n$ with
min-entropy at least $k$ (i.e., $\Pr[X=x] \leq 2^{-k}$ for
every $x$), then $X$ is a convex combination of distributions
that are uniform over subsets of $\bits^n$ of size at least
$2^k$. See footnote for hint\footnote{\textbf{Hint:} \tiny you
can use Farkas' Lemma (see Note 17.5).}
\end{question}
\begin{question} Prove the following slightly relaxed version of Lemma~16.34:
that if $X$ is a distribution over $\bits^n$ with min-entropy
at least $2k/\delta$ and $h$ is chosen from a pairwise
independent hash function family from $\bits^n$ to $\bits^k$,
then the distribution $h(X) \circ h$ is within statistical
distance at most $10\delta$ from $U_k \circ h$ (where $\circ$
denotes concatenation and $U_k$ denotes the uniform
distribution over $\bits^k$).
\end{question}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}