\documentclass[11pt]{article}   
\usepackage{fullpage}
\usepackage{amsfonts}

\newcommand{\F}{{\mathbb F}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\newcommand{\poly}{\mathop{\rm poly}}
%\input{dansmacs}

\begin{document}

\noindent {\large Advanced Complexity Theory \hfill 
Madhu Sudan\\[-.1in]
6.841/18.405J \hfill  \mbox{}\\[-.1in]
Due:  Wednesday, April 3, 2002\hfill \mbox{}\\[.4in]}
{\LARGE \centering Problem Set 3 \\[.4in] \par}


\section*{Problems}

\begin{enumerate}
\item An $n\times n$ matrix $A = \{a_{i,j}\}$ is a 
{\em Toeplitz} matrix if $a_{i+1,j+1} = a_{i,j}$ 
for every $1 \leq i < n$ and $1 \leq j < n$.
In this question all arithmetic will modulo $2$, i.e.,
in the field $\F_2$.

For a Toeplitz matrix $A \in \F_2^{n\times n}$, and
a vector $b \in \F_2^n$, let $h_{A,b}:\{0,1\}^n \to\{0,1\}^n$
be the function $h_{A,b}(x) = Ax + b$.
Let $H$ be the collection of functions $\{h_{A,b} | 
A \in \F_2^{n\times n}, b \in \F_2^n\}$.

Prove that $H$ is a nice, pairwise independent family of 
hash functions.

\item The birthday ``paradox'' says that if $a_1,\ldots,a_{m}$
are independent random numbers from the set $\{1,\ldots,N\}$
and $m = \omega(\sqrt{N})$ then, with probability almost one,
there exist $i\ne j \in \{1,\ldots,m\}$ such that $a_i = a_j$.

Derive upper and lower bounds on the probability of this 
event, as a function of $m$ and $n$, if $a_1,\ldots,a_m$
are pairwise independent random variables (distributed uniformly
from $\{1,\ldots,n\}$.

\item 
A function $f:\{0,1\}^* \to \Z^{\geq 0}$ is $\alpha$-approximated
by a function $g:\{0,1\}^* \to \Z^{\geq 0}$ if for every
$x \in \{0,1\}^*$, $f(x) \leq g(x) \leq \alpha f(x)$.
The $\alpha$-approximation problem for a function $f$ is that of
computing any function $g$ that $\alpha$-approximates $f$.

\begin{enumerate}
\item Define a promise problem that is 
equivalent to the $2$-approximation problem for $\#$SAT (where
$\#$SAT maps a 3CNF formula $\phi$ to the number of satisfying
assignments that $\phi$ has).
Include a proof of the equivalence.
\item 
Show that the $2$-approximation problem for $\#$SAT is
equivalent to the $4$-approximation problem.
\end{enumerate}

\newcommand{\perm}{{\mathop{\rm perm}}}
\item  Recall the definition of the permanent of 
a matrix. Let $S_n = \{\pi:[n]\to[n]$ s.t. $\pi$ is a 
permutation$\}$. Then for an $n\times n$ matrix $M = \{m_{ij}\}$
$\perm(M) = \sum_{\pi \in S_n} \prod_{i=1}^n m_{i\pi(i)}$.

Give a polynomial time algorithm to compute the 
permanent, modulo two, of an $n \times n$ integer matrix.

\item Show that it is \#P-complete to compute the number of
cycles in a directed graph. You may assume it is \#P-complete
to compute the number of Hamiltonian cycles in a directed graph.

\end{enumerate}

\noindent {\bf Instructions:}
\begin{itemize}
\item Usual rules on collaboration and references.
\item Turn in the solutions to the above problems by 11am on
Wednesday, April 3, 2002.
\end{itemize}

\end{document}