\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage{amssymb}
\newcommand{\1}{\mathbbm{1}}
\DeclareMathOperator*{\argmin}{argmin}
\DeclareMathOperator*{\argmax}{argmax}
\newcommand{\x}{\times}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\E}{\mathop{\mathbb{E}}}
\renewcommand{\bar}{\overline}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\eps}{\varepsilon}

\newcommand{\DTIME}{\textbf{DTIME}}
\renewcommand{\P}{\textbf{P}}
\newcommand{\SPACE}{\textbf{SPACE}}
\newcommand{\ds}{\displaystyle}

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

\handout{CS 221 Computational Complexity, Lecture 11}{Feb 27, 2018}{Instructor:
Madhu Sudan}{Scribe: Andrei Ciupan}{Approximate Counting and Parity}

\section{Goals for today $\ds \&$ Reminders}

\begin{enumerate}
\item Today we will:
\begin{enumerate}

\item Introduce approximate counting
\item Introduce the theorem Parity $\ds \notin AC^0$

\end{enumerate}
\item Office hours today 5-6PM
\item Pset 3 due this Friday

\end{enumerate}

\section{Introduction}
Last time we introduced $\ds \#\P$ and Permanent. In the following lectures we will be using counting arguments for our results. Today we focus on approximate counting and Parity.

\section{Approximate counting}

\begin{definition}
Consider a function $\ds f:\{0, 1\}^* \mapsto \mathbb R^{\geq 0}$. A function $\ds A:\{0, 1\}^* \mapsto \mathbb R^{\geq 0}$ is an \emph{$\ds\alpha$ - approximation algorithm to $\ds f$} if for all $\ds x$ of length $\ds n$, we have $$\ds \frac{f(x)}{\alpha(n)}\leq A(x) \leq f(x)\cdot \alpha(n).$$
\end{definition}

\begin{definition}
An approximation scheme for $\ds f$ is a collection of approximation algorithms such that for all $\ds \epsilon >0$ there exists a $\ds (1+\epsilon)$ approximation algorithm for $\ds f$ in polynomial time.
\end{definition}

A stronger notion is the following:

\begin{definition}
A Fully Polynomial Randomized Approximation Scheme is an approximation scheme composed of one algorithm such that for all $\ds\epsilon >0$, it produces a $\ds (1+\epsilon)$ approximation of $\ds f$  and runs in time $\ds poly\left(\frac{n}{\epsilon}\right)$ for inputs of length $\ds n$.
\end{definition}

Note many problems do not admit an approximation scheme:

\begin{enumerate}

\item An approximation to $\ds \#SAT$ determines whether the number of satisfying assignments is greater than zero

\item An approximation to $\ds \#Cliques(G)$ (the total number of cliques in a graph $\ds G$) solves the problem of counting the size of the largest clique in a graph. For a given graph $\ds G$ of $\ds n$ vertices, consider the graph $\ds G \times K_n$ defined as follows:

\begin{enumerate}

\item $\ds V(G\times K_n) = V(G)\times V(G)$ (the convention is that $\ds V(G')$ represents the set of vertices in a graph $\ds G'$.

\item There exists an edge between $\ds (v, w)$ and $\ds (v', w')$ in $\ds G\times K_n$ if and only if either $\ds v = v'$ or there exists an edge between $\ds v$ and $\ds v'$ in $\ds G$.

\end{enumerate}

Then if $\ds \omega(G)$ is the size of the maximal clique in $\ds G$ we have the following result: $$\ds 2^{n\cdot\omega(G)} \leq \#\mbox{ cliques in } G\times K_n \leq 2^{n\omega(G)}\cdot \left(\frac{n}{2}\right)^{\omega(G)}.$$

This implies that a $\ds \frac{2^n}{n^{\omega(G)}}$ - approximatin algorithm to $\ds \#Clique(G\times K_n)$ determines $\ds \omega(G).$

\end{enumerate}

\textbf{Exercise 1.} Prove the two claims above. The following results will be useful:
\begin{enumerate}

\item The number of cliques in a graph with $\ds n$ vertices and maximum clique size $\ds k$ is between $\ds 2^k$ and $\ds n^k$.

\item  $\ds \{(v_1, w_1), \dots, (v_q, w_q)\}$ is a clique in $\ds G\times K_n$ if and only if $\ds \{v_1, \dots, v_q\}$ is a clique in $\ds G$.

\end{enumerate}

Madhu also mentions that these kinds of approximate counting problems have also enjoyed a long history in the field of Monte Carlo algorithms. These also have complexity theoretic interpretations. Still there is a collection of nice results coming from approximations.

Jerrum - Valiant - Vazirani prove a generalization of the following result:

\begin{theorem}

There exists an approximate algorithm for counting the number of matchings in a graph $\ds G \iff $ there exists an approximate algorithm for uniformly sampling a matching in $\ds G$.

\end{theorem}

\begin{proof}

Assuming a $\ds (1+\epsilon)$ approximate counting algorithm $\ds \#Match(G)$ for the number of matchings in a graph $\ds G$, we construct a random sampling from the set of matchings in $\ds G$ as follows:

\begin{enumerate}

\item Pick a random edge $\ds e = (u, v) \in G$. With probability $\ds \frac{\#Match(G - \{u, v\})}{\#Match(G)}$ select $\ds e$. If an edge was selected, go to step $\ds 2$. Otherwise, repeat.

\item Let $\ds e = (u, v)$ be the most recently chosen edge. Repeat step 1 above for $\ds G \leftarrow G - \{u, v\}$, until we run out of vertices.

\item Output the set of edges chosen.

\end{enumerate}

The output of this algorithm gives a $\ds (1+\epsilon)^{O(n)}$ approximation for random sampling.

For the reverse implication we "invert" the previous process:

Pick an edge $\ds e = (u, v)$ from $\ds G$. Run the uniform sampler to estimate $\ds p$, the probability that edge $\ds e$ belongs to a matching of $\ds G$. 

\begin{enumerate}

\item If $\ds p < \frac{1}{2}$, recursively find the number of matchings in $\ds G - e$ and multiply it by $\ds \frac{1}{1-p}$. Note that in the graph $\ds G - e$ we just remove edge $\ds e$, not the endpoints.

\item If $\ds p \geq \frac{1}{2}$, recursively find the number of matchings in $\ds G - \{u, v\}$ and multiply it by $\ds \frac{1}{p}$. Note that in the graph $\ds G - \{u, v\}$ we remove edge $\ds e$ and the endpoints.

\end{enumerate}

\end{proof}

\textbf{Exercise 2.} Prove (hint: by induction) that in the second implication above, we obtain an error of $\ds (1+\epsilon)^{O(\mbox{\# edges in G})}$ if the error of the sampler is $\ds 1+\epsilon$.

\textbf{Exercise 3.} Prove that approximating the number of cycles in a graph is NP-hard.

Hint: reduce from Hamiltonian Cycle.

\bigskip

Now we move on to the second part of today's class: 

\section{ Approximate counting and known complexity classes }

\textbf{Exercise 4.} If PH has a complete problem, then it collapses.

\begin{theorem}
Approximate counting is in $\ds \Sigma_3^P$.
\end{theorem}

\begin{proof}

We will show that given a boolean formula $\ds \phi$, distinguishing between whether the number of satisfying assignments is $\ds \geq 2^{k+1}$ and $\ds \leq 2^k$ is in $\ds \Sigma_3^P$.

The idea is to find a collection of hash functions $\ds \{h_i\}$ which satisfy pairwise independence, such that if the number of satisfying assignments is "small", then the number of satisfying assignments hashed to zero is small, and if the number of satisfying assignments is large, then the number of satisfying assignments hashed to zero is also large.

\textbf{Exercise 5.} Complete this proof. Hint : it is in the same spirit as the proof from lecture 10.

\end{proof}

\begin{remark} Just like we saw the amplification argument in the previous lectures, we can see a similar one here: in order to increase the number of satisfying assignments of a CNF formula, one can consider the "squared" formula on twice the number of variables, which simply repeats the initial formula twice. The number of satisfying assignments to this formula is the square of the number of satisfying assignments of the original one. This allows us to amplify the gap in the number of satisfying assignments, if needed (for example for a result like the theorem above).

\end{remark}

\begin{theorem}
Toda's theorem : $\ds PH\subseteq \#P$ ( we will revisit this later in the course)
\end{theorem}

\begin{theorem}
 There exists an oracle $\ds A$ such that $\ds PH^A \neq \#P^A$
\end{theorem}

\begin{theorem}

Parity $\ds \notin AC^0$.

\end{theorem}

\begin{proof}

We prove that if a circuit of depth $\ds d$ computes parity for an input of length $\ds n$, then its size is at least $\ds 2^{\frac{1}{2}n^{1/2d}}$.

The idea is to prove that any proper polynomial of degree $\ds \sqrt{n}$ in $\ds \mathbb F_3$ differs from parity on at least $\ds \frac{2^n}{50}$ inputs, while there exists a proper polynomial of degree $\ds \sqrt{n}$ that differs from any circuit of size $\ds s$ and depth $\ds d$ on at most $\ds 2^{n - \frac{1}{2}\cdot n^{1/d}}$ inputs.

Combining these two gives the result as it implies that the size of the circuit can't be polynomial.

\end{proof}

\end{document}

