
\documentclass[10pt]{article}
\usepackage{amssymb}
\usepackage{graphicx}

\newtheorem{quest}{Question}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{5}{March 25, 2009}{Ronitt Rubinfeld}{Inbal Marhaim, Naama Ben-Aroya}

%%%% body goes in here %%%%

\section*{Today}
\begin{itemize}
\item Uniform generation of DNF satisfying assignments
\item Uniform generation and approximate counting
\end{itemize}

\section{Disjunctive Normal Form}
\begin{definition}
%\[F:\set{0,1}^n\rightarrow\set{0,1}\]
In Boolean logic, a \emph{disjunctive normal form} (DNF) is a standardization (or normalization) of a logical formula which is a disjunction of conjunctive clauses, such as:
\[F=x_{1}\bar{x_{2}}\vee x_{2}x_{4}\bar{x_{5}}\vee\dots\]
\end{definition}
\subsection{Questions}
\begin{quest}
Is the formula satisfiable?
\end{quest}
Yes, unless $F=0$.
\begin{quest}
\textbf{The counting problem:} How many assignments satisfy $F$?
\end{quest}
Let $\#F$ denote the number of satisfying assignments to the formula $F$.
\newline First we notice that \begin{center} $F$ is a DNF $\iff \bar{F}$ is a CNF \end{center}
therefore \begin{center} $\#F < 2^n \iff \bar{F}$ is satisfiable
\end{center}
Since 'Is CNF formula is satisfiable?' know to be hard ($NP$-complete) - the counting problem for DNF is also hard.
\begin{quest}
Can we generate a uniformly random satisfying assignment for a DNF formula?
\end{quest}

\section{Generate a Random Satisfying Assignment}
Naive algorithm: Pick a random assignment.\begin{itemize}\item If satisfies $F$, output it. \item Else, repeat.\end{itemize}
Problem: run time: $\Omega(\frac{1}{p})$, where $p=\frac{\#F}{2^n}$.
\subsection{One-Term DNF}
Example:\[F=x_{1}\bar{x_{2}}\]
Random satisfying assignment: set $x_{1}=1,x_{2}=0$, set all other variables randomly.
\newline
In general: set the variables of the clause to satisfy it and all other variables randomly. For one-term DNF it easy to compute $\#F$: if it's (only) clause has $k$ variables then $\#F=2^{n-k}$.
\subsection{Two-Term DNF}
Let $S_{i}$ denote the set of satisfying assignments of $F_{i}$.
\subsubsection{Disjoint Sets: $S_{1}\cap S_{2}=\emptyset$}
In this case: $\#F=|S_{1}\cup S_{2}|=2^{n-k_{1}}+2^{n-k_{2}}$.
Uniform generation: Pick $S_{i}$ with probability $\frac{|S_{i}|}{|S_{1}|+|S_{2}|}$. Output random element of $S_{i}$.
\subsubsection{Non Disjoint Sets: $S_{1}\cap S_{2}\neq \emptyset$}
The previous algorithm is OK for assignments from $S_{1}\triangle S_{2}$ ($=(S_{1}\setminus S_{2})\cup(S_{2}\setminus S_{1})$), but assignments from $S_{1}\cap S_{2}$ get twice as much probability.

Uniform generation: Pick $S_{i}$ with probability $\frac{|S_{i}|}{|S_{1}|+|S_{2}|}$. Pick random element of $S_{i}$. \begin{itemize}
\item If in $S_{1}\triangle S_{2}$ then output it.
\item Else (it is in $S_{1}\cap S_{2}$): toss a coin. If 'Heads' - output, else do whole procedure again.
\end{itemize}
\subsection{General Case: $F=F_{1}\vee F_{2}\vee\dots\vee F_{m}$}
\begin{tabbing}
\bf{Algorithm A:}\= \\
\> Step 1: \= \{Pretend $S_{i}$'s disjoint to pick element\} \\
\> \> Pick clause $i \in [m]$ with probability $\frac{|S_i|}{\sum |S_j|}$. \\
\> \> Then pick a random satisfying assignment $\pi$ to clause $i$. \\
\> Step 2: \= \{Compensate for intersections\} \\
\> \> Compute $\ell = |\{ j \in [m]: \pi \in S_j \}|$ (= number of clauses satisfied by $\pi$).\\
\> \> Then \= toss a coin with bias $\frac{1}{\ell}$. \\
\> \> \> If `Heads' - output $\pi$ and halt.\\
\> \> \> Else, start over.\\
\end{tabbing}
\begin{claim}
Algorithm A outputs each satisfying assignment $\pi$ with same probability.
\end{claim}
\begin{proof}
\begin{eqnarray*}
\Pr[\textrm{pick $\pi$ in Step 1}] &=& \sum_{\textrm{clause i that satisfied by $\pi$}}\Pr[\textrm{pick clause i}]\cdot \Pr[\textrm{output $\pi |$ picked $i$}]\\&=& \sum_i \frac{|S_i|}{\sum |S_j|}\cdot \frac{1}{|S_i|} = \frac{\ell}{\sum |S_j|}
\end{eqnarray*}
\begin{eqnarray*}
\Pr[\textrm{output $\pi$}] = \frac{\ell}{\sum |S_j|}\cdot \frac{1}{\ell} = \frac{1}{\sum |S_j|}
\end{eqnarray*}
So the probability to pick a random assignment is a constant, moreover it does not depend on the number of clauses it satisfied.
\end{proof}
\begin{claim}
$$E[\textrm{\# loops until output something}]\le m.$$
\end{claim}
\begin{proof-idea}
Since all biases in Step 2 are $\ge \frac{1}{m}$.
\end{proof-idea}
\section{P-relation}
\begin{definition}
$R\subseteq \{0,1\}^*\times\{0,1\}^*$ binary relation on strings. $R$ is a \emph{p-relation} if \begin{itemize}
\item $\forall(x,y)\in R: |y|=poly(|x|)$.
\item $\exists$ poly-time decision procedure for deciding whether $(x,y)\in R$.
\end{itemize}
\end{definition}
Examples:
\begin{itemize}
\item $R_{SAT}=\{(x,y)|x\textrm{ is a formula, }y\textrm{ is a satisfying assignment to }x\}$
\item $R_{matching}=\{(x,y)|x\textrm{ is a graph, }y\textrm{ is a perfect matching in }x\}$
\end{itemize}
\begin{theorem}
$L\in NP \textrm{ iff  } \exists \textrm{p-relation }R ~s.t.~$
\[x\in L\iff \exists y ~s.t.~ (x,y)\in R\].
\end{theorem}
\begin{definition} 
A function $f:\{0,1\}^* \rightarrow \mathbb{N}$ is in \emph{$\#P$} iff $\exists$ p-relation $R$ s.t. $\forall x$, $f(x) = |\{y|(x,y)\in R\}|$.
\end{definition}
\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.8]{Lecture5-b_pic3.jpg}
\label{fig:pic3}
\caption{\#P complexity class}
\end{center}
\end{figure}
$f(x)$ is the number of witnesses for an input $x$, which can each be validated in polynomial time.\\
It was shown that the counting problem for DNF (i.e. How many different variable assignments will satisfy a given DNF formula?) is $\#P$-complete.\\
Examples:
\begin{itemize}
\item $\#SAT$ - The number of satisfying assignments to a given formula
\item $\#Matching$ - The number of perfect matches\footnote{A matching is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex. A perfect matching is a matching which matches all vertices of the graph.} in a given graph
\end{itemize}

\begin{definition} 
$A$ is an \emph{approximate counter} for $f$ if \[\forall x \Pr[f(x)/(1+\epsilon) \leq A(x) \leq f(x)(1+\epsilon)] \geq 3/4\]If the runtime of $A$ is polynomial in $1/\epsilon$, $|x|$, then $A$ is a \emph{fully polynomial randomized approximation scheme (FPRAS)}
\end{definition}
* Note that in Homework 1, we have shown that $3/4$ can be replaced by any $1-\delta$ $(0<\delta<1)$, repeating $A(x)$ $O(log 1/\delta)$ times.

\begin{observation}
There is no FPRAS for $\#CNF$ (assuming $NP \neq RP$). 
If there were, then we could give a randomized algorithm to solve $SAT$ in polynomial time.  
\begin{itemize}
\item $SAT(x)$=yes $\Rightarrow \#CNF(x) > 0 \Rightarrow $FPRAS$(x) > 0$, with
  probability $\geq 3/4$. 
\item $SAT(x)$=no $\Rightarrow \#CNF(x) = 0 \Rightarrow $FPRAS$(x) = 0$, with
  probability $\geq 3/4$. 
\end{itemize}
Therefore, if we had an FPRAS for $\#CNF$, we could answer $SAT$ correctly with
 probability at least $3/4$.
\end{observation}

\begin{definition}
$R$ is a p-relation, $f:\{0,1\}^* \rightarrow \mathbb{N}$ s.t. $f(x) = |\{y|(x,y)\in R\}|$. $M$ is a \emph{uniform - generator} for $R$ if on input $x$
\begin{itemize}
\item $M$'s runtime is polynomial in $|x|$
\item if $f(x) > 0$ then $\forall y$ s.t. $(x,y)\in R$ $\Pr[M$ outputs $y] = 1/f(x)$
\item $M$ does not output $y$ s.t. $(x,y)\notin R$ ($M$ might not output anything)

\end{itemize}
\end{definition}
Example: The random assignment generator for DNF we saw. The probability the generator will return an assignment is equal for all the assignments, therefore it is equal to $1/f(x)$, while $f(x)$ is the number of assignments.

\begin{definition}
$R$ is a p-relation, $f:\{0,1\}^* \rightarrow \mathbb{N}$ s.t. $f(x) = |\{y|(x,y)\in R\}|$. $M$ is an \emph{almost uniform generator (AUG)} for $R$ if on input $x$
\begin{itemize}
\item $M$'s runtime is polynomial in $|x|$, $[1/\epsilon]$
\item if $f(x) > 0$ then $\forall y$ s.t. $(x,y)\in R$ $1/f(x)(1+\epsilon) \leq \Pr[M$ outputs $y] \leq (1+\epsilon)/f(x)$
\item $M$ does not output $y$ s.t. $(x,y)\notin R$ ($M$ might not output anything in this case)
\end{itemize}
\end{definition}

\begin{definition}[Jerrum, Valiant, Vazirani]
A problem is called \emph{self-reducible} if it can be solved via recursion on smaller problems of the same type.
\end{definition}
 The formal definition can be found in Jerrum, Valiant and Vazirani's work.\\
Example: SAT - $\varphi(x_1, \dots, x_n)$ is satisfiable if $\varphi(0, x_2, \dots, x_n)$ or $\varphi(1, x_2, \dots, x_n)$ is satisfiable.
\newline
\newline
Note: the running time of each recursive step must be polynomial but the number of recursions can be large (even exponential).

\section{FPRAS and AUG for SAT}

\begin{theorem}[Jerrum, Valiant, Vazirani]
$R$ is a self-reducible p-relation, then $\exists$ FPRAS for $R$ iff $\exists$ AUG for $R$.
\end{theorem}
This theorem implies that if one can approximate the number of solutions of a problem, he can also generate uniformly a random solution for the problem and vice versa.
\newline
\newline
\begin{proof-idea}
We will prove the theorem for the \#SAT problem

\subsection{Building an AUG from a FPRAS}

First we will assume that there is an exact counter for \#SAT, and we will use it to build an AUG for \#SAT.
\newline

We will use the fact that SAT is self-reducible, and define a self-recursion tree for a SAT formula:
Let $b_1, \dots, b_j$ be the index of the node with setting of prefix of $x_1, \dots, x_j$ s.t. $x_i = b_i \space \forall i\in[j]$. 
\newline $F_{b_1, \dots, b_j}$ is a new formula on $n-j$ variables.

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{Lecture5-b_pic1.jpg}
\label{fig:pic1}
\caption{Self-Reducibility Tree}
\end{center}
\end{figure}

We will use the \#SAT exact counter to guide a ``random walk" from the root to a leaf.
\newline Let $b_1, \dots, b_k$ be the current node.
\begin{itemize}
\item Use the exact counter and compute
 
$f_0 = F_{b_1,\dots,b_k,0} = \#SAT \varphi(b_1, \dots, b_k, 0, x_{k+2}, \dots, x_n)$

$f_1 = F_{b_1,\dots,b_k,1} = \#SAT \varphi(b_1, \dots, b_k, 1, x_{k+2}, \dots, x_n)$
\item Go left with probability $f_0/(f_0+f_1)$, right with probability $f_1/(f_0+f_1)$
\item If $f_0 = 0$ and $f_1 = 0$ stop and output nothing
\item If reached a leaf output it

\end{itemize}

Notice that if there are satisfying assignments the counter will return a number that is bigger than zero for at least one of the sides, therefore the algorithm will always choose a sub-tree which contains satisfying assignments, and will eventually output one.
\newline

The result is a proper AUG since:
\begin{itemize}
\item The counter's runtime is polynomial in $|x|, 1/\epsilon$, it is called $2*n$ times, so the total runtime is polynomial in $|x|, 1/\epsilon$
\item $\forall$ SAT assignment $b_1, \dots, b_n$, 

$\Pr[$output $b_1, \dots, b_n]$ $= \frac{F_{b_1}}{F_{b_1} + F_{\overline{b_1}}} \cdotp \frac{F_{b_1b_2}}{F_{b_1b_2} + F_{b_1\overline{b_2}}} \cdotp \frac{F_{b_1b_2b_3}}{F_{b_1b_2b_3} + F_{b_1b_2\overline{b_3}}} \cdotp\dots = \frac{1}{F}$
\item If the formula has no assignments both $f_0$ and $f_1$ will be zero and M will stop and return nothing

\end{itemize}

We proved that using an exact counter we can build a proper AUG. What if we use a FPRAS with parameter $\epsilon'$?
In this case each multiplicand in the equation will be multiplied by $(1 + \epsilon')^2$ at most (the numerator can be multiplies by $(1 + \epsilon')$ at most and the denominator can be multiplied by $\frac{1}{(1 + \epsilon')}$ at least), and by $\frac{1}{(1 + \epsilon')^2}$ at least.
So an approximate counter yields each satisfying assignment with probability 
$\forall y$ s.t. $(x,y)\in R$ 
\begin{center}
    $\frac{1}{(1 + \epsilon')^{2n}F}$ $\leq$ $\Pr[M$ outputs $y]$ $\leq$ $\frac{(1 + \epsilon')^{2n}}{F}$.
\end{center} 
Thus, if we want an $\epsilon$-FPRAS for uniform generation, then it is sufficient to call the uniform counting $\epsilon'$-FPRAS where $\epsilon' < \epsilon/2n$. 

\subsection{Building a FPRAS from an AUG}
We want to estimate the number of satisfying assignments using an almost uniform generator.
We only need an accuracy of $(1 + \epsilon)$ multiplication factor, so even if one of the sub-problems, say $F_1$, has only one member and the AUG will always return assignments which belong to $F_0$, this will still fit the required accuracy.
\newline

We will use an AUG to estimate the number of satisfying assignments:
\begin{itemize}
\item Pick $k$ random satisfying assignments using the AUG
\item Compute 

$S_{b_1}$ = the fraction of samples beginning with $b_1$

$S_{b_1b_2}$ = the fraction of samples beginning with $b_1b_2$

\dots

$S_{b_1b_2\dots b_n}$ = the fraction of samples beginning with $b_1b_2\dots b_n$
\item Estimate $F$ via $\frac{F_{b_1}}{S_{b_1}}$ ($S_{b_1} \approx \frac{F_{b_1}}{F})$:

$\hat{F} = \frac{\hat{F_{b_1}}}{S_{b_1}} = \frac{\hat{F_{b_1b_2}}}{S_{b_1}S_{b_1b_2}} = \frac{\hat{F_{b_1b_2b_3}}}{S_{b_1}S_{b_1b_2}S_{b_1b_2b_3}} = \dots = \frac{1}{S_{b_1}S_{b_1b_2} \dots S_{b_1b_2\dots b_n}}$

\end{itemize}

\begin{figure}[h]
\begin{center}
\includegraphics[scale=0.7]{Lecture5-b_pic2.jpg}
\label{fig:pic2}
\caption{A ``Random Walk" Illustration}
\end{center}
\end{figure}

This is a recursive process which simulates a ``walk" on the recursion tree of the formula. In each step of the recursion the algorithm should choose a ``direction"- on which sub-tree to continue the computation. We will choose $b_i\in\{0,1\}$ in each step such that maximizes the fraction of samples in its sub-tree $S_{b_1 \dots b_i}$.
In order to ensure a good estimation of $F$ we need:
\begin{enumerate}
    \item to reach a satisfying leaf - We will always reach a satisfying leaf (unless the formula is unsatisfiable) since we always recurse on the sub-tree with maximum samples.
\item $S_{b_1, \dots, b_k}$ to be a good approximation - We always recurse on the sub-tree with maximum samples. When one side has probability $1/2 - \alpha$ and the other side has probability $1/2 + \alpha$ (for small $\alpha$), we can show that the probability for sampling error is less then $e^{-2k\alpha^2}$ (by Chernoff bound). Therefore, for greater $\alpha$ we have smaller probability for picking the wrong sub-tree, and if $\alpha$ is very small then both sides has probability close to $1/2$ and picking each side will generate good approximation.
%, assuming there is no sampling error we will have each probability $> %\frac{1}{2}$. But what if we have a sampling error? This is only a problem when o%ne side has $1/2 - \alpha$ samples and the other side has $1/2 + \alpha$ %samples (for small $\alpha$), then we might have chosen the wrong side.
\end{enumerate}
The result is a FPRAS with $\epsilon '=\frac{\epsilon}{2n}$.
\end{proof-idea} 

\textbf{Conclusion:} We showed a way to generate a random satisfying assignment for DNF. Using the above theorem we proved that we have an approximate algorithm for \#DNF.

\end{document}




