\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}}
% 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 2006 - 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 1$^{st}$ to \textbf{May 15$^{th}$ 1:30pm}. The
exam needs to be submitted to \textbf{Mitra Kelly (Room 323)} by May
15$^{th}$ 1:30 pm. \emph{This is a strict deadline}. You may submit
the exam earlier. If you typed up your exam, I would appreciate it
if you also email me a copy of it at the same time. In any case,
please email me when you have submitted the exam.
\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 your 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. I recommend that you first write a draft solution
of all questions before writing (or preferably, typing) up your
final submitted exam.
\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 theorems that were proven in
class. You can also use without proofs 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 date and number the result
was proven, or to the place in the textbook where the result is
stated. 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{Points:} The exam has $6$ questions, with each worth $20$
points (total of $120$ points).
%\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
11am 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 $6$ questions, each worth $20$ points, summing up to $120$ points. \end{center}
\begin{question} Prove that if $\np=\p$ then there exists a function
$f$ in $\cclass{E} = \dtime(2^{O(n)})$ and a constant $\e>0$ such
that $f$ can not be computed by circuits of size $2^{\e n}$.
\end{question}
\begin{question} We say that a language $L \subseteq \bits^*$ is
\emph{sparse} if there exists a polynomial $p:\N\To\N$ such that for
every $n$, $|L \cap \bits^n| \leq p(n)$. We say that $L$ is
\emph{$\np$-complete} if there exists a polynomial-time computable
function $f$ such that for every 3CNF formula $\varphi$, $\varphi
\in \tsat \iff f(\varphi) \in L$.
\begin{enumerate}
\item Prove that if a sparse language $L$ is $\np$-complete then the
polynomial hierarchy collapses.
\item Prove that if a sparse language $L$ is $\np$-complete then
$\np=\p$. (Hint: think of downward self-reducibility and dynamic
programming.)
\end{enumerate}
\end{question}
\begin{question} Let $f = \{ f_n \} \in \aco$. Prove that $f$ can be $90\%$-approximated by
a family of circuits $\{ C_n \}$ where each circuit $C_n$ is of
polynomial-size, depth three, and consists of a single unbounded
fanin parity gate at the top, and polynomially many $\wedge$ and
$\vee$ gates, each with polylogarithmic fanin. (We assume that
$\neg$ gates are at the bottom, or equivalently the inputs to the
circuit are $x_1,\ldots,x_n,\overline{x}_1,\ldots,\overline{x}_n$,
for simplicity you may assume the circuit also gets the constants
$0$ and $1$ as additional inputs.) An $n$-input circuit $C$
$90\%$-approximates a function $f:\bits^n\To\bits$ if for a random
$x\getsr\bits^n$, $C(x)=f(x)$ with probability $\geq 0.9$.
\end{question}
\begin{question} Throughout this course, we often used the fact
that for every $x\in \bits^n$ with $x \neq 0^n$, $\Pr_{r\getsr
\bits^n}[ \iprod{x,r} \pmod{2} = 1 ] = 1/2$. We now ask whether we
can choose $r$ using fewer than $n$ random bits.
\begin{enumerate}
\item Prove that for every $\e>0$ there exists a set $S \subseteq \bits^n$ of size
$\poly(n,1/\e)$ such that
\begin{equation}
\tfrac{1}{2} - \e < \Pr_{r\getsr S}[
\iprod{x,r} \pmod{2} = 1 ] < \tfrac{1}{2} + \e \label{eq:lintest}
\end{equation}
\item Let $S$ be a set satisfying (\ref{eq:lintest}) for $\e \leq 1/10$ and let $A$ be
an $|S|\times n$ matrix whose rows are elements of $S$. Prove that
the function $ECC:\bits^n\To\bits^{|S|}$ defined as follows: $ECC(x)
= Ax$ is an \emph{error correcting code} with distance at least
$1/4$. That is, for any $x \neq x' \in \bits^n$ the fractional
Hamming distance of $ECC(x)$ and $ECC(x')$ is at least $1/4$.
\item Show an explicit construction of a set $S$ of size $\poly(n)$
that satisfies (\ref{eq:lintest}) for $\e = 1/10$. That is, show a
polynomial-time algorithm that on input $1^n$ outputs the list of
elements of such a set $S$.
\end{enumerate}
\end{question}
\begin{question} Call a set $S$ satisfying (\ref{eq:lintest}) above
``$\e$-nice''.
\begin{enumerate}
\item For a set $S \subseteq \bits^n$, let $S'$ be the corresponding subset
of $\pmo^n$ (where we identify $\bits$ with $\pmo$ in the usual way
of $0 \mapsto +1$ , $1 \mapsto -1$). Consider the function
$f:\pmo^n\To\R$ defined as follows: for $x\in\pmo^n$, $f(x)=1$ if
$x\in S'$ and $f(x)=0$ otherwise. As in class, for $\alpha \subseteq
[n]$ and $x\in\pmo^n$ let $\chi_{\alpha}(x) = \prod_{i\in\alpha}
x_i$ and $\Hat{f}(\alpha) = \Ex_{x \getsr \pmo^n}[
f(x)\chi_{\alpha}(x) ]$.
Let $\mu = \tfrac{|S|}{2^n}$. Prove that $\Hat{f}(\emptyset)=\mu$
and that if $S$ is $\e$-nice then for $\alpha \neq \emptyset$,
$|\Hat{f}(\alpha)| \leq 2\mu\e$.
\item Let $S$ be an $\e$-nice set. Define a graph $G$ with $2^n$
vertices and degree $|S|$ as follows: we put an edge between $x,y
\in \bits^n$ if $x \oplus y \in S$. Recall that $\lambda(G)$ denotes
the absolute value of the second-largest eigenvalue of the
normalized adjacency matrix of $G$. Prove that if $S$ is $\e$-nice
then $\lambda(G) \leq 2\e$. (Hint: the family of $2^n$ eigenvectors
for this matrix is quite natural.)
\end{enumerate}
\end{question}
\begin{question} We define a \emph{non-deterministic} circuit to be
a Boolean circuit $C$ that takes two inputs $x\in\bits^n$ and
$y\in\bits^m$ where we define that $C$ accepts the input $x$ iff
$\exists y\in\bits^n$ such that $C(x,y)=1$ (i.e., we think of the
second input as a witness/certificate for the first input). Recall
the language $\gni$ containing pairs of adjacency matrices of graphs
that are \emph{not} isomorphic. Prove that $\gni$ can be decided by
a polynomial-sized family $\{ C_n \}$ of non-deterministic circuits
(i.e., for every $x\in \bits^n$, $C_n$ accepts $x$ iff $x\in \gni$.)
Note that it's not known whether or not $\gni \in \np$.
\end{question}
\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}