\documentclass[10pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts,amssymb}
\usepackage{graphicx}
\usepackage{subfigure}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem{example}{Example}
\newtheorem{conjecture}{Conjecture}
%\usepackage{epsfig}
\begin{document}
\input{preamble.tex}
\lecture{23}{May 7, 2007}{Madhu Sudan}{Alex Andoni, Anastasios Sidiropoulos}
%%%% body goes in here %%%%
\section{Overview}
Topics for this lecture are:
\begin{itemize}
\item
Continue the discussion on Average-Case analysis (as opposed to Worst
Case);
\item
Present Impagliazzo's five possible worldsl
%\item
%$DNP\not\in AvgTime(n^c)$ (NOT covered in
\end{itemize}
Administrativia:
\begin{itemize}
\item
Project presentations are on Wed and Thu in 32-G531
and 32-G631 respectively;
\item
Email comments on PCP and Average-Case lectures by Tuesday.
\item
Fill out HKN Survey online.
\end{itemize}
\section{Literature on Average-Case Complexity}
Some of important surveys on average case complexity (very far from
being all of them) are, in approximate chronological order:
\begin{itemize}
\item
Levin~\cite{Lev} formalized the idea that average case complexity is about
problems {\it plus a distribution} over inputs (i.e., hardness depends
on the the distribution).
\item
Impagliazzo~\cite{Imp} wrote a survey giving his ``Personal View of
Average-Case Complexity'' describing 5 possible worlds (we live in
exactly one of them; we just don't know which one, yet).
\item
Goldreich wrote a survey, that made its way into his book~\cite{Gold}.
\item
Ajtai~\cite{Ajt-ICM} gave a talk at ICM'02 on connections between
Worst-Case complexity and Average-Case Complexity, specifically, in
the context on lattice problems.
\item
Bogdanov and Trevisan~\cite{BT-Survey} recently wrote a survey on
``Average-Case Complexity''.
\end{itemize}
In this lecture, we discuss Impagliazzo's five possible worlds, as
well as Ajtai's lattice problems.
\section{Impagliazzo's five possible worlds}
Russell Impagliazzo wrote a survey on Average-Case
Complexity~\cite{Imp} describing 5 possible worlds: we live in one of
them, but do not yet know which one.
The motivation for the classification is to relate cryptography to
worst-case/average-case complexity. A question raised by
Diffie-Hellmann was whether we can base cryptography on strong
assumptions such as $\mathrm P\neq \mathrm{NP}$. Today we can't, and
there are roughly 3 questions that, at the moment, seem relatively
independent:
\begin{itemize}
\item ${\mathrm P}\neq {\mathrm NP}$;
\item
Existence of one-way functions (defined below). This implies some cryptography
(Diffie-Hellmann's protocol);
\item
Existence of Public Key CryptoSystems (PKCS) (best example of it is,
of course, RSA).
\end{itemize}
The only implications we know are that PKCS implies existence of
one-way functions, which, in turn, imply ${\mathrm P}\neq {\mathrm
NP}$. Where does the truth lie?
\begin{definition}
A {\em one-way function} is a function $f:\{0,1\}^*\to \{0,1\}^*$ such
that it is easy to compute but hard to invert on average, i.e.:
\begin{itemize}
\item[Easy:] Computing $f(x)$ takes $poly(|x|)$ time;
\item[Hard:] Given a random $x\leftarrow U_n$ (uniform over
$\{0,1\}^n$), it is hard to invert $f(x)$, that is for any poly-time
probabilistic-time algorithm $A$, we have that
$$
\Pr_{x\leftarrow U_n}[A(f(x))\in f^{-1}(f(x))]=\mathrm {neglijible}.
$$
(Note that it would be too harsh to require that $A$ returns $x$
precisely since $f(x)$ migth have simply lost this information.)
\end{itemize}
\end{definition}
These considerations led to the definitions of $\mathrm{DNP}$ and
$\mathrm{Avg-BPP}$.
Impagliazzo's five worlds roughly assume different scenarios of
validity of the above questions.
To put worlds in a perspective, he uses the story of
Gauss's class in school, and his Professor Grouse. The idea is that
Professor Grouse wants to humiliate Gauss in front of the class by
giving him (inventing) a problem that Gauss cannot solve. In each of
the 5 worlds, we will see whether Professor manages to humiliate Gauss
or not. In these considerations, we assume that both Professor Grouse
and Gauss are poly-time algorithms\footnote{Impagliazzo leaves it
unspecified whether these are deterministic or randomized or even
quantum algorithms.}.
\begin{enumerate}
\item {\bf [Algorithmica]} The world where $\mathrm
P=\mathrm{NP}$. Then we have efficient algorithms for all NP-complete
problems. Professor Grouse cannot embarass Gauss since Gauss can
efficiently solve all problems that Professor Grouse can give him
(well, at least from the class of problem that do have an efficiently
describable solution/proof).
\item {\bf [Heuristica]} ${\mathrm P}\neq \mathrm{NP}$ but
$\mathrm{DNP}\subseteq \mathrm {Avg-BPP}$. In some sense there are
hard instances to NP-complete problems, but it's hard to find those
instances (they are not poly-time sample-able).
Professor Grouse cannot humiliate Gauss by giving a hard problem
(unless he spends a lot of time looking for such problem, say,
polynomially more time than Gauss uses to solve it).
Note that this world is still different from Algorithmica, even ``in
practice'' (see Impagliazzo paper for details).
\item {\bf [Pessiland]} In this world, the world of a pessimist,
$\mathrm{DNP}\not\subseteq \mathrm {Avg-BPP}$ but one-way functions
don't exist. The first condition says it is easy to come up with hard
instances (there are poly-time sampleable distributions that are
hard). However, the second condition says that it is hard to generate hard
instances together with the answers (since we can invert the
generation process and find the random bits used to generate
problem+solution).
The implication for Professor Grouse is that he can humiliate Gauss
but in a very restricted sense. Professor Grouse can give Gauss a hard
problem, but he will not know the answer to his own question!
Although in this ``grey world'', NP-complete problems are hard, and crypto
does not exist, there are some positive implications.
\item {\bf [Minicrypt]} In this world, one-way functions exist but not
PKCS. Some limited form of cryptography is possible.
Professor Grouse can finally humiliate Gauss: Professor Grouse can
generate problems, together with solutions, such that Gauss cannot
solve these problems.
\item {\bf [Cryptomania]} PKCS exist, and we can regain some
confidence in e-Commerce.
Professor Grouse can stage a superior form of humiliation, in addition
to the above form of humiliation. Professor Grouse can choose the
``dumbest'' student in the class (on the fly), and then, generate a
problem that Gauss cannot solve but this dumbest student {\em can}
solve. All this happens in a public setting (no private channel
between the professor and the dumbest student).
\end{enumerate}
The last world seems most believable.
\section{Random 3SAT}
There are some ``empirical'' approaches to solving hard problems (NP)
in average-case (i.e., take a problem and solve on ``random''
instances). However, so far, people have tried and failed. One of the
illustrative directions is Random 3SAT problem.
% (besides computer scientists,
%this problem is interesting to statistical physists, probability
%theorists).
For a 3CNF formula $\phi$ with $m$ clauses on $n$ variables, we define
the \emph{density} of $\phi$ to be the ratio $\Delta(\phi)=m/n$. For
each $\delta>0$, $n>0$, we define a distribution ${\cal D}_{\delta,n}$
on 3CNF formulae on $n$ variables with density $\delta$ as follows.
For a given number of variables $n$, we pick $m=\delta\cdot n$
clauses, where for each clause we pick 3 literals uniformly at random.
The resulting average-case computational problem is referred to as
\emph{Random 3SAT}.
The study of the behavior of Random 3SAT has attracted a lot of
attention in Statistical Physics, and Probability Theory in general.
It is easy to see that for density $\delta$ close to 0, the
probability that a clause in ${\cal D}_{\delta,n}$ tends to 1.
Moreover, for density $\delta$ close to $\infty$, this probability
tends to 0. In fact, it has been conjectured that there exists a
phase transition on the fraction of satisfiable formulae of density
$\delta$, around some density $\Delta_0\approx 4.2$. More precisely,
\begin{conjecture}\label{conj1}
There exists $\Delta_0\approx 4.2$, such that
\begin{itemize}
\item
For each $\Delta<\Delta_0$, $\lim_{n\rightarrow \infty}\mathbf{Pr}_{\phi\in {\cal D}_{\Delta,n}}[\phi \mbox{ is satisfiable}] = 1$.
\item
For each $\Delta>\Delta_0$, $\lim_{n\rightarrow \infty}\mathbf{Pr}_{\phi\in {\cal D}_{\Delta,n}}[\phi \mbox{ is satisfiable}] = 0$.
\end{itemize}
\end{conjecture}
Note that if the above conjecture is true, then Random 3SAT is easy
for all densities $\Delta\neq \Delta_0$: one can simply output YES if
the density of the given formula is greater than $\Delta_0$, and NO
otherwise. In fact, all (heuristic) algorithms that are currently
known for Random 3SAT fail for densities close to $\Delta_0$. This
fact lead to the formulation of the following computational
conjecture.
\begin{conjecture}\label{conj2}
If we pick a random 3CNF formula $\phi$ of density $\Delta_0$, then it is hard to tell if $\phi$ is satisfiable.
\end{conjecture}
The above conjecture implies that $\mbox{DNP}\subsetneq \mbox{Avg-BPP}$.
On the other hand, one could also formulate an opposite conjecture:
\begin{conjecture}\label{conj3}
There exists a polynomial-time algorithm $A$, and a family of formulae $\{S_n\}_{n\in \mathbb{N}}$, such that
\begin{itemize}
\item
$\mathbf{Pr}_{\phi\in {\cal D}_{\Delta_0, n}}[\phi\in S_n]$ is negligible.
\item
For each $\phi \notin S_n$, $A(\phi)=\mbox{SAT}(\phi)$.
\end{itemize}
\end{conjecture}
Note that conjectures \ref{conj1} and \ref{conj3} can be simultaneously true.
That is, a phase transition in Random 3SAT might not necessarily imply a computational hardness on average for density $\Delta_0$.
In fact, Ben-Sasson has shown that there exists an NP-hard problem that gives rise to a phase transition with respect to some appropriate parameter, yet it is easy on average for every possible value of this parameter.
\section{Shortest Vector Problem}
Ajtai used problems based on lattice to introduce a worst-case problem $\Pi_1$ which is not known to be in $P$, that can be reduced to a distributional problem $(\Pi_2, D)$.
A lattice $L$ in $\mathbb{Q}^n$ is defined as a discrete additive subset of $\mathbb{Q}^n$. That is, for each $x,y\in L$, $x+y\in L$, and $x-y\in L$, and also there exists $\epsilon>0$, s.t.~for each $x\in L$, $\mbox{Ball}(x,\epsilon)\cap L=\{x\}$.
The length of the shortest vector in $L$, denoted by $\lambda_1(L)$ is defined as the minimum distance between two elements in $L$.
A lattice in $\mathbb{Q}^n$ can be given represented by a set of vectors $b_1,\ldots,b_n\in \mathbb{Q}^n$, such that
\begin{itemize}
\item
$b_1,\ldots,b_n$ are linearly independent.
\item
$L=\{\sum_{i\in [n]} r_i\cdot b_i | r\in \mathbb{Z}^n\}$.
\end{itemize}
Therefore, with the above representation a lattice can be given as
input to an algorithm. The computational problem SVP of finding
$\lambda_1(L)$ is notoriously hard.
One can define an approximate version of SVP, called
$\mbox{Approx-SVP}_g$ as follows. Given a lattice $L$ by its basis
$(b_1,\ldots,b_n)$, output a non-zero vector $v\in L$,
s.t.~$\|v\|_2\leq g(n)\cdot \lambda_1(L)$.
It has been shown that for each polynomial $g_2$, there exists a
polynomial $g_1$, such that the worst-case problem
$\mbox{Approx-SVP}_{g_1}$ can be reduced to the distributional problem
$(\mbox{Approx-SVP}_{g_2}, D_{g_2})$.
Moreover, Coldreich and Coldwasser have shown that the problem
$\mbox{Approx-SVP}$ cannot be NP-hard.
Feigenbaum and Fortnow, and Bogdanov and Trevisan have shown that if
there exists a many-one reduction from SAT to the same DNP problem
$(\Pi,D)$, then PH collapses.
\bibliographystyle{alpha}
\begin{thebibliography}{alpha}
\bibitem{Lev} Leonid Levin. Average Case Complete Problems. SIAM
J. Comp. 15 (1986), pp. 285-286.
\bibitem{Imp} Russell Impagliazzo. A Personal View of Average-Case
Complexity. 1995.
\bibitem{Gold} Oded~Goldreich. {\em Computational Complexity: A
Conceptual Perspective}. In preparation. Available
at~\texttt{http://www.wisdom.weizmann.ac.il/~oded/cc-book.html}.
\bibitem{Ajt-ICM} Mikl\' os Ajtai. Worst-Case Complexity, Worst-Case
Complexity and Lattice Problems. {\em Doc. Math. J. DMV} III,
pp. 421-428. Extra Volume ICM 1998.
\bibitem{BT-Survey} Andrej Bogdanov and Luca Trevisan: Average-case
complexity. In {\em Foundations and Trends in Theoretical Computer
Science}, volume 2, issue 1, Now Publishers, 2006.
\end{thebibliography}
\end{document}