\documentclass[10pt]{article}

\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}

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

\begin{document}
\input{preamble.tex}
\newcommand{\card}[1]           {\left| #1\right|}
\newcommand{\defn}[1]           {{\textit{\textbf{\boldmath #1}}}}
%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{9}{March 8, 2006}{Ronitt Rubinfeld}{Kunal Agrawal}

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

\section{Previous Lecture}

We saw how to generate random satisfying assignments to a DNF formula.  In
this lecture, we see how to approximately count the number of satisfying
assignments to a DNF formula.  

\section{Definitions} 

\begin{definition} $R\subseteq \{0,1\}^* \times \{0,1\}^*$ is
  \defn{p-relation} if 
\begin{itemize}
\item $\forall (x,y) \in R, \card{y} = \poly(\card{x})$
\item $\exists$ p-time decision procedure for deciding $(x,y) \in R$
\end{itemize}
\end{definition}

Example: $R_{SAT} = \{(x,y)| x \mbox{ is a formula, }y \mbox{ is a
  satisfiable assignment}\}$ 

\begin{definition} $f:\{0,1\}^* \rightarrow \mathbb{N}$
ia in \defn{$\#P$} iff $\exists$ p-relation $R$ s.t. $\forall x, f(x) = \card{\{y | (x,y)
    \in R\}}$
\end{definition}

In other words, a problem is in $\#P$ if and only if the number of witnesses for the problem are polynomial in the size of the problem.  
$\#P$-complete problems are the hardest problems in $\#P$.  $\#CNF$, $\#DNF$
and $\#MATCHING$ are all $\#P$-complete problems.


\begin{definition} ${\cal A}$ is an \defn{approximate counter} for $f$ iff
  $\forall x, \Pr[ f(x)/(1+\varepsilon) \leq {\cal A}(x) \leq
    f(x)(1+\varepsilon)] \geq 3/4$.  If the runtime of ${\cal A}$ is $\poly(\card{x},
  1/\varepsilon)$ then ${\cal A}$ is a ``fully polynomial randomized approximation
  scheme'' (FPRAS). 
\end{definition}

\begin{observation} There is no FPRAS for $\#CNF$.  If there were,
  then we could give a randomized algorithm to solve $SAT$ in polynomial time.  
\begin{itemize}
\item $SAT(x)$=yes $\implies \#CNF(x) > 0 \implies $FPRAS$(x) > 0$, with
  probability $\geq 3/4$. 
\item $SAT(x)$=no $\implies \#CNF(x) = 0 \implies $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$. This implies that if there existed FPRAS for
 $SAT$, so we would know that $NP=RP$.
\end{observation}

\begin{definition}
$R$ is a p-relation, $f:\{0,1\}^* \rightarrow \mathbb{N}$ s.t. $f(x) =
\card{\{y|(x,y) \in R\}}$.
$M$ is a \defn{uniform generator} for $R$ if on any $x$
\begin{itemize}
\item $M$'s runtime is $\poly(\card{x})$, and
\item if $f(x) > 0$, then $\forall y$ s.t. $(x,y) \in R, \Pr[M\mbox{ outputs
  }y] = 1/f(x)$.
\end{itemize}
\end{definition}

\begin{definition}
$R$ is a p-reln, $f:\{0,1\}^* \rightarrow N$ s.t. $f(x) =
\card{\{y|(x,y) \in R\}}$.
$M$ is a \defn{almost uniform generator} for $R$ if on any $x, \varepsilon$
\begin{itemize}
\item $M$'s runtime $\poly(\card{x},1/\varepsilon)$, and
\item if $f(x) > 0$, then $\forall y \mbox{ such that } (x,y) \in R,$ then $1/((1+\varepsilon)f(x)) \leq
  \Pr[M\mbox{ outputs }y] \leq (1+\varepsilon)/f(x)$.
\end{itemize}
\end{definition}

Here is the definition of self-reducibility given in the work of Jerrum, Valiant and Vazirani:

\begin{definition}
A relation $R \subseteq \Sigma^* \times \Sigma^*$ is \defn{self-reducible}
iff
\begin{enumerate}
\item There exists a polynomial time computable function $g: \Sigma^* \rightarrow {\cal N}$
such that if $xRy$ then $|y| = g(x)$.
\item There exists a polynomial time computable function $\psi: \Sigma^* \times \Sigma^* \rightarrow \Sigma^*$
and $\sigma:\Sigma^* \rightarrow {\cal N}$ satisfying
\begin{itemize}
\item $\sigma(x) = O(\log{|x|})$
for all $x \in \Sigma^*$
\item if $g(x)>0$ then $\sigma(x)>0$ 
for all $x \in \Sigma^*$
\item $|\psi(x,w)| \leq |x|$
for all $x,w \in \Sigma^*$
\item for all $x \in \Sigma^*$, $y=y_1,\ldots,y_n \in \Sigma^*$, \\
$<x,y_1,\ldots,y_n> \in R$ iff $<\psi(x,y_1,\ldots,y_{\sigma(x)}),y_{\sigma(x)+1},\ldots,y_n> \in R$
\end{itemize}
\end{enumerate}
The function $g$ gives the length of the solutions to instances, and
$\sigma$ gives the granularity of solutions as follows: Given instance $x$
and initial segment $w$ of a witness $y$ for $x$ (i.e., $(x,y) \in R$),
$\psi$ gives an instance $x'$ whose solutions are exactly those words which
when concatenated with $w$ form witnesses to $x$.
\end{definition}

For the purposes of this lecture, self-reducibility means solving a problem
by solving smaller problems.  $SAT$ is self-reducible.  If we had an oracle $P$
that solved a problem with $n-1$ variables, then you can use it to solve a problem
with $n$ variables, to solve  $SAT(\Phi(x_1 \dots x_n))$:
\begin{enumerate}
\item If $P(\Phi(0,x_2, \dots x_n))$ = satisfiable, or $P(\Phi(1,x_2,\dots, x_n)) =$
  satisfiable, 
\item output satisfiable,
\item else output unsatisfiable.
\end{enumerate}

\section{FPRAS for $\#DNF$}

Most graph and optimization problems are self-reducible.  Today, we use
this property to show prove a theorem of by Jerrum, Valiant and Vazirani.

\begin{theorem}[Jerrum, Valiant, Vazirani]
If $R$ is a self-reducible P-relation, there is an FPRAS for $R$ iff there is
  a almost uniform generator (aug) for $R$.   
\end{theorem}

The theorem means that approximate counting is equivalent to
approximate uniform generation.  We are going to do the proof of $SAT$,
and the only thing we use it is that $SAT$ is self-reducible.
\subsection{Reducing approximate uniform generation to approximate counting}

For simplicity, first, we assume that we have an exact counter of
$\#SAT$, and generate exact uniform generator.  Then we relax this assumption
to get an approximate generation from an approximate counter.  

We use a \defn{self-reducibility tree} and each node of this tree
corresponds to the settings of a prefix\footnote{There was a question in
class about what happens if two prefixes of a witness reduce to the same
subproblem.  This is not be a problem, since as long as the prefixes are
different, the witness that would be output would be distinct at each
leaf.}\@.  The tree is shown in \ref{fig:pic1}.  At each node we get a
formula, $\Phi_{b_1...b_j}(x_{j+1}...x_n)=\Phi(b_1,...b_j,
x_{j+1}...x_n)$. The leaves are the full assignments.  If we had an oracle
for counting the number of solutions on both the right and the left subtree
of each node, then we can just do a biased random walk of the tree to
generate a solution uniformly at random.

\begin{figure}
\begin{center}
\includegraphics[scale=0.6]{l9pic1.eps}
\label{fig:pic1}
\caption{Self-Reducibility Tree}
\end{center}
\end{figure}

Let the current node be $(b_1...b_j)$, 
\begin{itemize}
\item Use the exact counter to compute 
$S_0 = F_{b_1..b_j,1}$ and 
$S_1 =  F_{b_1..b_j,0}$
\item Go left with probability $S_0/(S_0+S_1)$ and right with probability $S_1/(S_0+S_1)$.
\item output the leaf you reach.
\end{itemize}

The output is correct because for any assignment $(b_1,...,b_n) =b$ that
the algorithm outputs, 
\begin{itemize}
\item $b$ is definitely a satisfying assignment.
\item 
\begin{equation}
\Pr[\mbox{output }b]=\frac{F_{b_1}}{F}\frac{F_{b_1,b_2}}{F_{b_1}}\frac{F_{b_1,b_2,b_3}}{F_{b_1,b_3}}... = 1/F.
\end{equation}
\end{itemize}

Now we prove that an approximate counter can be used in an approximate
uniform generator using exactly the same algorithm.  What if we were using
an $\varepsilon'$-FPRAS for counting instead of an exact counter?  The right
hand side of the equation becomes: $(1/F)(1+\varepsilon')^n/(1-\varepsilon')^n
\leq (1/F)(1/(1-\varepsilon)^{2n})$.  Thus, if we want an $\varepsilon$-FPRAS for
uniform generation, then it is sufficient to call the uniform counting
$\varepsilon'$-FPRAS where $\varepsilon' < \varepsilon/2n$.

\subsection{Reducing approximate counting to approximate uniform generation}

Again, first, let us assume that we have a perfect uniform generator for
$R_{SAT}$, and try to get an approximate counter.  We will then relax the
assumption and use the approximate generator.  We look at the
self-reducibility tree, and let $S_1=F_1/F$.  We are interested in
computing the number of solutions to the formula, which is $F=F_1/S_1$.
$S_1$ can be computed by sampling, that is, generating some uniformly
distributed satisfying assignments (using our oracle for uniform
genetation) and taking the ratio of the ones where $x_1=1$ and those with
$x_1=0$.  $F_1$ can be computed recursively.

Since we can only generate approximately uniform satisfying
assignments, we can compute $F_1$ and $S_1$ approximately.  Approximations
are represented with hats on the variables.  
\begin{enumerate}
\item For $b \in
\{0,1\}$.  Let $\hat{S}_b=$ Number of samples beginning with
  b/total number of samples 
\item Now recursively estimate $F_b$ by
$\hat{F}_b$.  
\item Estimate $F$ via $\frac{\hat{F}_b}{\hat{S}_b}$.
\end{enumerate}
Unrolling the recursion gives us: 
\begin{eqnarray*}
\hat{F} &=& \frac{\hat{F}_{b_1}}{\hat{S}_{b_1}} \\ 
&=& \frac{\hat{F}_{b_1b_2}}{\hat{S}_{b_1}\hat{S}_{b_1b_2}}\\ 
&=& ... \\
&=& \frac{1}{\hat{S}_{b_1}\hat{S}_{b_1b_2}...\hat{S}_{b_1b_2...b_n}} 
\end{eqnarray*}

If we had exactly uniform generators and no sampling errors, then the
recursion can go either left or right, as long as the subtree had some
satisfying assignment.  But since we only have approximate generators, we
recurse on the subtree which has more satisfying assignments.  We need to
estimate each $\hat{S}_{b_1...b_j}$ to within $\varepsilon/2n$ factor.  Which
gives $\hat{F} \leq (1+\varepsilon)F$ and $\hat{F} \geq 1/(1+\varepsilon)F$.

There is a slight technical problem with using Chernoff bounds in this
case, which forces us to recurse on the side which we think has more
satisfying assignments.  The Chernoff bound says that:
\begin{eqnarray*}
\Pr[\hat{S_b} > (1+\delta)] \leq e^{-\delta^2 S_b m /3}
\end{eqnarray*}
where $m$ is the number of samples.  When $S_b$ is very small, then the
number of samples needed to estimate the $\hat{S_b}$ upto reasonable accuracy
gets bigger.  Therefore, we need to go down the side with more satisfying 
assignments.  

%% As long as $\hat{S_b} \geq 1/4$, we have The additive chernoff bound gives you a multiplicative
%% result.  

%% if $p \geq 1/4$, then $p+\varepsilon/8 = p(1 + \varepsilon/8p) \leq p (1+
%% \varepsilon/8)$.  

%% Always go down the side that is atleast a quarter, (and since the sum is
%% 1).  As long as the sampling error is not over a quarter, then p is atleast
%% a quarter and it all works out.  

  
\end{document}