\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}