%% LyX 1.6.0 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{geometry}
\geometry{verbose,letterpaper}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newtheorem{thm}{Theorem}
  \theoremstyle{definition}
  \newtheorem{defn}[thm]{Definition}
  \theoremstyle{remark}
  \newtheorem{rem}[thm]{Remark}
  \newtheorem{lem}[thm]{Lemma}
 \ifx\proof\undefined\
   \newenvironment{proof}[1][\proofname]{\par
     \normalfont\topsep6\p@\@plus6\p@\relax
     \trivlist
     \itemindent\parindent
     \item[\hskip\labelsep
           \scshape
       #1]\ignorespaces
   }{%
     \endtrivlist\@endpefalse
   }
   \providecommand{\proofname}{Proof}
 \fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\usepackage{epsfig}

\makeatother

\usepackage{babel}

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

\lecture{4}{March 18, 2009}{Ronitt Rubinfeld}{Itay Kirshenbaum,
Oren Zomer, Margarita Vald}


\section{Introduction}

Today: 
\begin{itemize}
\item Another application of hashing 

\begin{itemize}
\item But first: 

\begin{itemize}
\item Interactive proofs 
\item Graph nonisomorphism 
\item Public Vs. Private coins 
\end{itemize}
\item Interactive proofs to lower bound set sizes 
\end{itemize}
\item Uniform generation of combinatorial objects 
\end{itemize}

\section{Interactive Proofs}


\subsection{Definitions}

\begin{defn}$NP$ = All decision problems for which proof of \textquotedbl{}yes\textquotedbl{}
answers can be verified by a polynomial time deterministic Turing
Machine \end{defn} \begin{defn}{\em Interactive Proofs System
(IPS)} {[}Goldwasser Micali Rackoff] \end{defn} %
\begin{figure}[htp]
\setlength{\epsfysize}{100pt} \vspace{3mm}
 \centerline{\epsfbox{ip.eps}} 

\caption{Interactive Proof System Protocol}


\label{fig:ips} 
\end{figure}


An {\em Interactive Proofs System} for language $L\subseteq\set{0,1}^{*}$
is a protocol for $V(Verifier),P(Prover)$ such that: 
\begin{itemize}
\item If $V,P$ follow protocol and $x\in L$ then $\Pr_{\text{v's coins}}[\text{V accepts x}]\geq\frac{2}{3}$ 
\item If $V$ follows protocol and $x\notin L$ then $\Pr_{\text{v's coins}}[\text{V accepts x}]\leq\frac{1}{3}$ 
\end{itemize}
\begin{defn}{\em Interactive Proofs (IP)} = \set{L | L\text{
has IPS}} \end{defn} \begin{defn}{\em Isomorphism} \end{defn}
Graphs $G=(V_{G},E_{G})$, $H=(V_{H},E_{H})$ are said to be isomorphic
($G\cong H$) if $V_{H}=\pi(V_{G})$ such that $(u,v)\in E_{G}\Leftrightarrow(\pi(u),\pi(v))\in E_{H}$

\begin{defn}{\em Graph Isomorphism:} $L_{GI}=\set{(G,H)|G\cong H}$
\end{defn} \begin{defn}{\em Graph Non-Isomorphism:} $L_{GNI}=\set{(G,H)|G\ncong H}$
\end{defn}


\subsection{Graph Non-Isomorphism}

\begin{thm}$GNI\in IP$ {[}Goldreich Micali Wigderson] \end{thm}

\begin{proof} Protocol: 
\begin{itemize}
\item Input: Graphs $G,H$ ($P$ claims $G\ncong H$) 
\item $V$ computes: 

\begin{itemize}
\item $G'$ a random permutation of $G$ 
\item $H'$ a random permutation of $H$ 
\end{itemize}
\item Do twice: 

\begin{itemize}
\item $V$ flips coin: 

\begin{itemize}
\item If Heads: $V$ sends $(G,G')$ to $P$ 
\item If Tails: $V$ sends $(G,H')$ to $P$ 
\end{itemize}
\item $P$ sends $V$ $\cong$ or $\ncong$ 
\item $V$'s response:


\begin{tabular}{lcr}
 &  & \tabularnewline
$V$'s flip  & $P$'s response  & $V$'s output \tabularnewline
\hline 
Heads  & $\cong$  & continue \tabularnewline
Tails  & $\ncong$  & continue \tabularnewline
Heads  & $\ncong$  & FAIL \tabularnewline
Tails  & $\cong$  & FAIL \tabularnewline
\end{tabular}

\end{itemize}
\item Output \textquotedbl{}accept\textquotedbl{} 
\end{itemize}
\end{proof}

\begin{proof} Correctness of Protocol: 
\begin{itemize}
\item If $(G,H)\in L_{GNI}$, that is $G\ncong H$, unlimited time $P$
can figure out the coin because $G\cong G'$ and $G\ncong H'$, and
always answers correctly so $\Pr[V\text{accepts}]=1\geq\frac{2}{3}$ 
\item If $(G,H)\notin L_{GNI}$, that is $G\cong H$, $P$ may not follow
the protocol, but he can do no better than random guessing (Since
the distribution on $V$'s messages is identical when flips Heads/Tails)
- Can get $V$ to continue with probability $\frac{1}{2}$ in each
loop. More formally: 

\begin{itemize}
\item WLOG $P$ is deterministic, that is a fixed function of $(G,\tilde{H})$ 
\item Some $q$ fraction of permutations $\pi's$ cause $P(G,\pi(G))$ to
answer $\ncong$, so (Heads, $\ncong$) will cause failure 
\item $1-q$ fraction of permutations $\pi's$ cause $P(G,\pi(G))$ to answer
$\cong$, so (Tails, $\cong$) will cause failure 
\item $H'$ is a uniformly distributed random permutation of $H$ and $H\cong G$,
therefore $H'$ is a uniformly distributed random permutation of $G$.
$G'$, by definition, is a uniformly distributed random permutation
of $G$. Therefore $\tilde{H}$ will be a uniformly distributed random
permutation of $G$. 
\item $\Pr[$V$\text{ fails}]=\frac{1}{2}q+\frac{1}{2}(1-q)=\frac{1}{2}$ 
\item Enough to run the loop twice to get $\Pr[V\text{accepts}]=\frac{1}{4}\leq\frac{1}{3}$ 
\end{itemize}
\end{itemize}
\end{proof}


\section{Public Coins vs. Private Coins}

A generalization of the Interactive Proof model is in making the outcome
of the coins that the verifier tosses \emph{public}. This small change
leads to a model of Proofs called Arthur-Merlin games or {}``IP public''.
It is known that the ''public'' proof model, i.e. Arthur-Merlin
games, and the {}``private'' proof model are equivalent.(Sipser
and Goldwasser) and anything you can do in IP without access to random
bits you can do with access to random bits.

In Arthur-Merlin games the idea is that Arthur (the verifier) flips
random coins at each round, but unlike the private coins model, the
coins are visible to Merlin (the prover) as well. Merlin then tries
to persuade Arthur of the answer. Note that since Merlin is all-powerful,
he does not need to see anything but the coin-tosses of Arthur, because
once Merlin knows the coin tosses, he can compute what Arthur is going
to ask. 
\begin{defn}
A \emph{round} is a communication round, where messages are sent from
the prover to the verifier and vice versa in one direction only. 

For example IP protocol for $GNI$ is three rounds protocol.
\end{defn}
The behavior of the Verifier $V$ (Arthur) can then be described as
follows:
\begin{description}
\item [{if}] all $k$ rounds are done $V$\ decides whether to accept
or reject
\item [{if}] less then $k$ rounds are done, $V$ outputs some random bits 
\end{description}
This leads to complexity classes $AM(k)$ and $MA(k)$, where $k$
is the number of rounds and the order of letters A and M is determined
by who (Arthur or Merlin) starts the conversation.


\subsection{Graph Automorphisms}
\begin{defn}
An \textit{automorphism} of a graph $G=(V,E)$ is a permutation $\pi$
of the vertex set $V$, such that for any edge $e=(u,v),\pi(e)=(\pi(u),\pi(v))$
is also an edge in $E$. (That is, it is a graph isomorphism from
$G$ to itself ). The identity mapping of a graph onto itself is called
the \emph{trivial automorphism} of the graph (See for example figures
\ref{fig:-has-six} and \ref{fig:-has-only}).
\end{defn}
%
\begin{figure}[h]
\begin{center}\includegraphics[scale=0.5]{nontrivial}\end{center}

\caption{\label{fig:-has-six}$G$ has six automorphisms $1\rightarrow A,2\rightarrow B,3\rightarrow C;1\rightarrow B,2\rightarrow A,3\rightarrow C$
etc...}

\end{figure}


%
\begin{figure}[h]
\begin{center}\includegraphics[scale=0.5]{trivial2}\end{center}

\caption{\label{fig:-has-only}$G$ has only the trivial automorphism $1\rightarrow A,2\rightarrow B,3\rightarrow C,4\rightarrow D,5\rightarrow E,6\rightarrow F$ }

\end{figure}


We're about to prove that $GNI\in IP-Public$ but we'll show it only
for a special case of graph-nonisomorphism. In this special case,
we prove the non-isomorphism of two connected graphs, $A$ and $B$,
each with only the trivial automorphism. Let $n$ denote the number
of nodes in both $A$ and $B$. If they were different, the proof
of non-isomorphism would be trivial.

If $G$ is a graph, then let $[G]$ denote the set of graphs isomorphic
to $G$. All of the graphs in $[G]$ have the same set of vertices,
and all are obtained by permuting the vertices of $G$. However, a
pair of vertices might be adjacent in one graph in $[G]$, but not
in another.

For a graph $G$, the size of $[G]$ is $n!/|Aut(G)|$ where $n$
is the number of vertices in $G$ and $|Aut(G)|$ is the number of
automorphisms of $G$. Since the graphs $A$ and $B$ have only one,
trivial automorphism, $\left|[A]\right|=\left|[B]\right|=n!$ (See
figure \ref{fig:The-set-of})

%
\begin{figure}[h]
\begin{center}\includegraphics[scale=0.5]{iso}\includegraphics[scale=0.5]{noniso}\end{center}

\caption{\label{fig:The-set-of}The set of all permutation on $A$ and $B$.
The graph on the right shows the case where $A$ and $B$ are not
isomorphic. On the other hand the graph on the left shows the case
where $A$ and $B$ are isomorphic. }

\end{figure}


Define $U$ to be the set of graphs obtained by uniting $[A]$ and
$[B]$. As consequences, we obtain two fact that we will use extensively:
\begin{itemize}
\item If $A$ and $B$ are not isomorphic, then $\left|U\right|=|[A]\cup[B]|=2n!$
and we refer it as\textbf{ {}``large''}. 
\item If $A$ and $B$ are isomorphic, then $\left|U\right|=|[A]\cup[B]|=n!$
and we refer it as \textbf{{}``small''}. 
\end{itemize}

\subsection{IP-Public Protocol}
\begin{thm}
$GNI\in IP-Public$
\end{thm}
The overall idea is that the prover convinces the verifier that $\left|U\right|=|[A]\cup[B]|$
is big--- more like $2n!$ than $n!$. By the preceding facts, this
implies that $A$ and $B$ are not isomorphic.

The present problem is to determine whether a set is {}``a tiny fraction''
or {}``half a tiny fraction'' of a universe. In this case, the universe
$D_{n}$ is defined to be the set of all $n$ node graphs and let
$m$ be the number of bits needed to describe a n-node graph ($m=n^{2}$).
It is easy to see that $[A]\cup[B]$ is at most {}``a tiny fraction''
of this universe $D_{n}$. 

To see why this is a problem, consider the following procedure for
proving graph non-isomorphism. 
\begin{enumerate}
\item The verifier $V$ uses public coins to generate a random $n$ node
graph $G\in D_{n}$ and send it to $V$. 
\item If $G\in[A]\cup[B]=U$, then the prover $P$ returns a proof of this
fact in the form of a mapping between the vertices of $G$ and the
vertices of $A$ or $B$. 
\item The verifier looks at how often the prover returns a valid proof.
If $A$ and $B$ are not isomorphic, then $[A]\cup[B]$ is twice as
big as if they were isomorphic. This means that the prover can return
a valid proof twice as often. The verifier detects this and concludes
that $A$ and $B$ are not isomorphic. Recall that $\frac{\#successes}{\#tries}\leq\frac{\left|U\right|}{\#graphs}$
\end{enumerate}
Note that \textbf{$\frac{\left|U\right|}{\#graphs}$} is exponentially
small. Hence, the flaw in this procedure is that a random graph $G\in D_{n}$
is so rarely in $U=[A]\cup[B]$--- whether $A$ and $B$ are isomorphic
or not--- that the number of rounds must be exponential for the verifier
to reach any conclusion and therefore, we won't be able to estimate
it in polytime. As an exercise, look at the Chernoff bounds and make
sure you see how the number of required samples depends on $\frac{\left|U\right|}{\#graphs}$.

The solution is to use hashing. The set $U=[A]\cup[B]$ is a tiny
fraction of $D_{n}$. But now we cleverly hash $D_{n}$ down to a
small set $S$. It will turn out that if $A$ and $B$ are not isomorphic,
then the image of $[A]\cup[B]$ under the hash function will be a
big fraction of $S$. If $A$ and $B$ are isomorphic, then the image
of $[A]\cup[B]$ will be only a small fraction of $S$. In this way,
hashing from $D_{n}$ to $S$ converts an {}``tiny fraction'' vs.
{}``half a tiny fraction'' problem in $D_{n}$ into a {}``big fraction''
vs. {}``small fraction'' problem in $S$ (See figure \ref{fig:Let--denote}).

%
\begin{figure}
\begin{center}\includegraphics[scale=0.5]{unihash}\end{center}

\caption{\label{fig:Let--denote}Hashing $m$ bit strings into $\ell$ bit
strings using randomly chosen pairwise independent function $h$.}



\end{figure}


To obtain the objective we need $h$ to have the following properties:
\begin{enumerate}
\item $\left|h\left(U\right)\right|\approx\left|U\right|$ i.e $h\left(U\right)$
is big iff $U$ is big
\item $\frac{\left|h\left(U\right)\right|}{2^{l}}$ is $\geq\frac{1}{poly\left(n\right)}$
\item $h$ computable in polytime (Since the verifier is going to have to
compute it).
\end{enumerate}

\subsection{Universal Hashing}
\begin{defn}
A family of functions $H=\left\{ h:\left\{ 0,1\right\} ^{m}\rightarrow\left\{ 0,1\right\} ^{\ell}\right\} $
is called \textit{pairwise independent} if for any $\alpha\neq\beta\,\in\left\{ 0,1\right\} ^{m}$
and for any $\gamma,\delta\,\in\left\{ 0,1\right\} ^{\ell}$:\[
Pr_{h}\left[h\left(\alpha\right)=\gamma\wedge h\left(\beta\right)=\delta\right]=2^{-2\ell}\]


Note that immediately from the definition it also follows that for
any $\alpha,\gamma$ (and some $\beta\neq\alpha$):\[
Pr_{h}\left[h\left(\alpha\right)=\gamma\right]=\underset{\delta}{\sum}Pr_{h}\left[h\left(\alpha\right)=\gamma\wedge h\left(\beta\right)=\delta\right]=2^{\ell}\cdot2^{-2\ell}=2^{-\ell}\]
\end{defn}
\begin{rem}
We'll be using the terms {}``universal hash functions'' and {}``pairwise
independent hash functions'' interchangeably.
\end{rem}
The family of all functions from $\left\{ 0,1\right\} ^{m}$ to $\left\{ 0,1\right\} ^{\ell}$
is universal, but is so large that even specifying a particular element
requires excessive space. Fortunately, more manageable universal hash
families exist. For example, the family $\left\{ h_{M,b}\left(x\right)=Mx+b\right\} _{M\in M_{\ell\times m},\, b\in\left\{ 0,1\right\} ^{\ell}}$
where $M_{\ell\times m}$ is the set of $\ell$ by $m$ binary matrices,
and the arithmetic is done in $GF\left(2\right)$, is pairwise independent
and form a universal hash family. In addition, in a previous lecture
we saw a construction of pairwise independent bits that would work
here as well.

Now we are ready to present an interactive proof protocol with public
coins for graph-nonisomorphism. Call the verifier $V$ and the prover$P$.

Let $H=\left\{ h:\left\{ 0,1\right\} ^{m}\rightarrow\left\{ 0,1\right\} ^{\ell}\right\} $
be a family of pairwise independent functions. Let $D_{n}$ be the
set of all n node graphs, encoded using $m$ bits. Let $U$ be the
subset of $D_{n}$ corresponding to graphs in $[A]\cup[B]$. Let $S$
be the set of 0-1 column vectors of size $\ell$ where $\ell$ will
be set later.
\begin{enumerate}
\item $V$ picks $h\in_{R}\, H$ and send $h$ to the $P$
\item $P$ sends to $V$ an element $x\in U$ s.t $h\left(x\right)=0^{\ell}$
and a proof that $x\in U$, where the proof is an automorphism from
$A$ or $B$ to $x$.
\item $V$ checks that $h(x)=0^{\ell}$ and checks $P$ proofs that $x\in U$.
If $x$ passes both checks, then $V$ accepts. 
\end{enumerate}
Note that if $U$ is {}``big'' then $P$ would be able to supply
an appropriate $x$ frequently and convince $V.$ But, if $U$ is
{}``small'' $P$ would be able to convince $V$ less often.

The following lemma is the tool we use to convert a {}``tiny fraction''
vs. {}``half a tiny fraction'' problem in $D_{n}$ into a {}``big
fraction'' vs. {}``small fraction'' problem in $S$.
\begin{lem}
\label{lem:hash-1} Let $H$ be a Pairwise independent family of hash
functions from $\left\{ 0,1\right\} ^{m}$ to $\left\{ 0,1\right\} ^{\ell}$.
Let $U$ be a subset of $\left\{ 0,1\right\} ^{m}$ and define $\alpha=|U|/2^{\ell}$.
Then
\end{lem}
\[
\alpha-\frac{\alpha^{2}}{2}\leq Pr_{h}\left[0^{\ell}\in h\left(U\right)\right]\leq\alpha\]

\begin{proof}
The right hand side is easy. \[
Pr_{h}\left[0^{\ell}\in h\left(U\right)\right]\leq\underset{x\in U}{\sum}Pr_{h}\left[0^{\ell}=h\left(x\right)\right]=|U|/2^{\ell}=\alpha\]
The left hand side is more tricky. \begin{eqnarray*}
Pr_{h}\left[0^{\ell}\in h\left(U\right)\right] & \geq & \underset{x\in U}{\sum}Pr_{h}\left[0^{\ell}=h\left(x\right)\right]-\underset{\underset{x\neq y}{{\scriptstyle x,y\,\in U}}}{\sum}Pr_{h}\left[0^{\ell}=h\left(x\right)=h\left(y\right)\right]\\
 & = & \alpha-\frac{\left(\begin{array}{c}
|U|\\
2\end{array}\right)}{\left(2^{\ell}\right)^{2}}\\
 & \geq & \alpha-\frac{\left|U\right|^{2}}{2}\cdot\frac{1}{2^{\ell}}\\
 & = & \alpha-\frac{\alpha^{2}}{2}\end{eqnarray*}
The first line uses an inclusion-exclusion principle truncated after
two terms. The second line follows from the definition of universal
hashing. The final line follows from the definition of $\alpha$.
\end{proof}

\subsubsection{Choice of $\mathbf{\ell}$}

Now all we need to do is to choose $\ell$. We pick $\ell$ s.t $2^{\ell-1}\leq2n!\leq2^{\ell}$
(See figure \ref{fig:The-setting-of}).

%
\begin{figure}
\begin{center}\includegraphics[scale=0.3]{pick_ell}\end{center}\caption{\label{fig:The-setting-of}The setting of the parameter $\ell$}

\end{figure}


First, suppose that $A$ and $B$ are not isomorphic. Then $\left|U\right|=|[A]\cup[B]|=2n!$,
and $1\geq\alpha\geq\frac{1}{2}$. Lemma~\ref{lem:hash-1} says that
\[
Pr_{h}\left[0^{\ell}\in h\left(U\right)\right]\geq\alpha-\frac{\alpha^{2}}{2}\geq\frac{3}{8}=c_{1}\]
Now, suppose that $A$ and $B$ are isomorphic. Then $\left|U\right|=|[A]\cup[B]|=n!$,
and $\alpha=|U|/2^{\ell}\leq\frac{1}{2}$. Therefor, \[
Pr_{h}[V\: accepts]\leq\alpha\leq\frac{1}{2}=c_{2}\]


The proof is not completely correct since we need $c_{1}>c_{2}$.
The solution to this problem is to run the protocol above three times
and accept iff $V$ accepted in all the three iterations.


\subsection{General Case Idea}
\begin{thm}
[Goldwasser-Sipser]IP with $k$ rounds $\subseteq$ IP-public with
$k+3$ rounds.
\end{thm}
We will restrict ourselves to $k=2$. Here is our 2-round interactive
proof. Let $\ell$ be our poly, and let $w$ be the word we are reasoning
about. As usual, we denote the verifier by $V$ and the prover by
$P$ . Let $r$ be $V's$ random bits.
\begin{enumerate}
\item $V$ gets a random string $r\in\{0,1\}^{\ell(|w|)}$. $V$ uses $r$
to produce a message $q$ ({}``$q$'' for {}``query'') and sent
$q$ to $P$.
\item $P$ answers with a response $a$; $P$ should answer with $a$ that
causes acceptance on most random strings that produce $q$.
\item $V$ checks $P$'s answer and accepts or rejects it.
\end{enumerate}
Assume $\left|q\right|=\left|a\right|=\left|r\right|=\ell$.

$V$ may be pictured as a map from random strings $r$ to questions
$q$. Any interesting IP protocol has $V$ not injective, because
otherwise $P$ knows what $r$ $V$ started with from $q$. We can
divide the $r$ into two types: those which, with $a$, cause acceptance,
and those which don't.
\begin{itemize}
\item Let $R(q)$ = \{$r\in\{0,1\}^{\ell(|w|)}$ s.t. $V(w,r)=q$\}
\item Let $a_{q}$ be chosen to maximize $Pr_{r}[V(w,r,q,a_{q})$ accepts]
s.t. $V(w,r)=q$
\item Let $A(q)=\left\{ r\in\{0,1\}^{\ell(|w|)}|\, V(w,r)=q\wedge V(w,r,q,a_{q})\: accepts\right\} $.
$A(q)$ are the random strings where $P$ has a good probability to
convince $V$ (See figure \ref{fig:6}).X
\item Let $A=\underset{q}{\cup}A(q)$ 
\end{itemize}
and therefore $Pr\left[V\: accepts\right]=\frac{|A|}{2^{\ell(|w|)}}$.

%
\begin{figure}[h]
\begin{center}\includegraphics[scale=0.4]{genCase}\end{center}

\caption{\label{fig:6}The partition of random bits into sets which ask the
same question. The shaded sets are where $P$ can make $V$ to accept
with good probability.}

\end{figure}
 

Note that where $x$ is in the language $\left|A\right|$ is big and
where $x$ is not in the language $\left|A\right|$ is small.


\subsection{MA(5) Simulation}

In the MA(5) protocol which solves whatever language the previous
IP(2) protocol did, $P$ will attempt to show that $|A|$ is big.
To do this, $P$ will demonstrate that for some $c$ and $d$, there
are at least $2^{c}$ $q$'s s.t., $|A(q)|\ge2^{d}$, which will imply
$|A|\ge2^{c+d}$ . If $|A|>2^{l-1}$, then $\exists c,d$ s.t. this
holds, where $2^{c+d}\ge\frac{2^{l-1}}{2l}$ (this can easily be verified
- simply show the converse is not true by considering the l possibilities
for c.) This requires performing the lower bound protocol on the number
of random strings causing $V$ to accept.

The rest of the proof is beyond the scope of the course.


\section{Disjunctive Normal Form}

A logical formula is considered to be in DNF if and only if it is
a disjunction of one or more conjunctions of one or more literals
(variables and their negation), such as: \[
F=x_{1}\bar{x_{2}}x_{3}\vee\bar{x_{1}}x_{2}x_{4}x_{5}\vee\dots\]
 In a later lecture we will look for algorithms that can output $\alpha$
such that \[
\frac{\#\text{satisfying assignments}}{(1+\epsilon)}\leq\alpha\leq(1+\epsilon)\cdotp\#\text{satisfying assignments}\]
 Every conjunction of k different literals (that do not contain a
variable and its negation) is satisfied by $2^{n-k}$ assignments,
where n is the total number of variables. The size of the union, however,
could be less than the sum of sizes. For example, in the case of 2
clauses: $F=x_{i_{1}}\dots\bar{x_{i_{k}}}\vee x_{j_{1}}\dots\bar{x_{j_{k}}}$
we can get: %
\begin{figure}[htp]
\setlength{\epsfysize}{100pt} \vspace{3mm}
 \centerline{\epsfbox{dnf.eps}} 

\caption{Satisfying Assignments of 2 Terms}


\label{fig:dnf} 
\end{figure}


The size of the union is the sum of sizes each term's satisfying assignments
minus the size of the intersection. 
\end{document}
