\documentclass[11pt, a4paper]{article} \usepackage{../mysty} \renewcommand{\lesson}{9} \renewcommand{\lessontitle}{Probabilistic reductions} \renewcommand{\fulltitle}{Lesson \lesson: \lessontitle} \usepackage{xr} %\externaldocument{../lesson-09/2020b-toc-note-09} %\externaldocument{../lesson-10/2020b-toc-note-10} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% START DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \date{} %\thispagestyle{empty} \begin{center} {\Large {\bf \fulltitle}} \end{center} \vspace{0.5cm} \noindent {\bf Theme:} Probabilistic reductions and preliminary to Toda's theorem. \section{Probabilistic reduction from $\sat$ to $\usat$} Let $\usat$ be the following language. \begin{eqnarray*} \usat & \defeq & \{\varphi: \varphi\ \text{is a boolean formula with unique satisfying assignment}\} \end{eqnarray*} \begin{theorem} \label{theo:valiant-vazirani} {\bf (Valiant and Vazirani, 1986)} There is a probabilistic polynomial time algorithm $\cM$ such that on input (Boolean) formula $\varphi$, the output of $\cM$, denoted by $\cM(\varphi)$, satisfies the following. \begin{itemize} \item If $\varphi \in \sat$, then $\prarg {\cM(\varphi)\in \usat} \geq 3/(16n)$, where $n$ is the number of variables in $\varphi$. \item If $\varphi \notin \sat$, then $\prarg {\cM(\varphi)\in \sat} =0$. \end{itemize} \end{theorem} \begin{proof} The algorithm $\cM$ works as follows. On input formula $\varphi$, do the following. \begin{itemize} \item Let $x_1,\ldots,x_n$ be the variables in $\varphi$. \item Let $x \defeq (x_1,\ldots,x_n)$. \item Randomly choose $k \in \{2,\ldots,n+1\}$. \item Randomly choose a hash function $h\in \cH_{n,k}$, where $\cH_{n,k}$ is pair-wise independent. \item Output the formula $\varphi(x) \wedge (h(x)=0)$, where $0$ is a column vector of zeroes of size $k$. \end{itemize} Note that the part $h(x)=0$ can be stated as a boolean formula. If we use the collection $\cH_{n,k}$ as in Theorem~\ref{theo:hash-exists-b}, $h(x)=0$ is of the form: $Ax+b=0$, which is equivalent to $Ax=b$. This can be written into the following form: $$ \bigwedge_{i=1}^k\ \Big(\big(A_{i,1} x_{1} \oplus \cdots \oplus A_{i,n}x_n\big) \ \iff \ b_i\Big) $$ Here $\oplus$ denotes the XOR operation. Note that each $A_{i,1} x_{1} \oplus \cdots \oplus A_{i,n}x_n$ can be rewritten into formulas using only $\wedge,\vee,\neg$ in quadratic time as follows. Divide it into two halves, rewrite each half (recursively) and combine them with the standard definition of XOR. Now, we prove the correctness of our algorithm. Obviously, if the input formula $\varphi$ is not satisfiable, so is the output formula. Suppose $\varphi$ is satisfiable. Let $S$ be the set of satisfying assignments of $\varphi$. With probability $1/n$, the algorithm chooses a value $k$ such that $2^{k-2}\leq |S|\leq 2^{k-1}$. By Lemma~\ref{lem:valiant-vazirani}, the probability that there is a unique $x\in S$ such that $h(x)=0$ is~$\geq 3/16$. Thus, the probability that $\cM(\varphi)\in \usat$ is at least $3/(16n)$. \end{proof} \section{The language $\paritysat$ and the class $\paritypt$} \label{sec:paritysat} The language $\paritysat$ is defined as follows. \begin{eqnarray*} \paritysat & \defeq & \{\varphi : \varphi\ \text{is a Boolean formula with {\em odd} number of satisfying assignments}\} \end{eqnarray*} The class $\paritypt$ is defined as follows. A language $L \in \paritypt$, if there is a polynomial time NTM $\cM$ such that for every input word $w$, $w\in L$ if and only if the number of accepting runs of $\cM$ on $w$ is odd number. We define a few terminology and notations. Let $\sharp\varphi$ denote the number of satisfying assignments of a (Boolean) formula $\varphi$. We will define operations $\sim$, $\sqcap$ and $\sqcup$ on formulas such that the following holds. $$ \sharp(\sim\varphi)=\sharp\varphi +1\qquad\qquad \sharp(\varphi\sqcap\phi)=\sharp\varphi \cdot \sharp\phi \qquad\qquad \sharp(\varphi\sqcup\phi)=(\sharp\varphi +1)\cdot(\sharp\phi +1)+1 $$ Obviously the following holds. \begin{eqnarray*} \sim\varphi\ \in \ \paritysat & \text{if and only if} & \varphi\ \notin\ \paritysat \\ \varphi\sqcap\phi\ \in\ \paritysat & \text{if and only if} & \text{both}\ \varphi,\phi\ \in\ \paritysat \\ \varphi\sqcup\phi\ \in\ \paritysat & \text{if and only if} & \text{at least one of}\ \varphi,\phi\ \in\ \paritysat \end{eqnarray*} These operations are defined as follows. \begin{itemize} \item For $\varphi$ with variables $x_1,\ldots,x_n$, we pick a ``new'' variable $z$ and define $\sim\varphi$ as follows. \begin{eqnarray*} \sim\varphi & \defeq & \big(\neg z \wedge \varphi\big) \ \vee \ \big(z\wedge \bigwedge_{i=1}^n x_i\big) \end{eqnarray*} \item For two formulas $\varphi$ and $\psi$, we rename the variables so that the variables in $\varphi$ and $\phi$ are disjoint, and define $\varphi\sqcap\psi$ as follows. \begin{eqnarray*} \varphi\sqcap\phi & \defeq & \varphi\wedge\phi \end{eqnarray*} \item For two formulas $\varphi$ and $\psi$, we rename the variables so that the variables in $\varphi$ and $\phi$ are disjoint, and define $\varphi\sqcup\psi$ as follows. \begin{eqnarray*} \varphi\sqcup\phi & \defeq & \sim(\sim\varphi \ \sqcap \ \sim\phi) \end{eqnarray*} \end{itemize} \section{Probabilistic reductions from $\sat$ and $\overline{\sat}$ to $\paritysat$} Theorem~\ref{theo:valiant-vazirani} can be easily extended to obtain reductions from $\sat$ and $\overline{\sat}$ to $\paritysat$. \begin{lemma} \label{lem:sat-to-paritysat} {\bf (Reduction from $\sat$ to $\paritysat$)} There is a polynomial time PTM $\cM$ that on input formula $\varphi$ and a positive integer $m$ (in unary), outputs a formula, denoted by $\cM(\varphi,m)$, such that the following holds. \begin{itemize} \item If $\varphi \in \sat$, then $\prarg {\cM(\varphi,m)\in\paritysat} \geq 1-2^{-m}$. \item If $\varphi\notin \sat$, then $\prarg {\cM(\varphi,m)\in \paritysat} =0$. \end{itemize} Moreover, the output $\cM(\varphi,m)$ uses $O(mn^2)$ variables, where $n$ is the number of variables in $\varphi$.\footnote{Abusing the notation, $O(mn^2)$ denotes $\leq cmn^2$, for some constant $c$.} \end{lemma} \begin{proof} On input $\varphi$ with $n$ variables, the algorithm $\cM$ first runs the reduction in Theorem~\ref{theo:valiant-vazirani} on $\varphi$ for $8mn$ times to obtain formulas $\psi_1,\ldots,\psi_{8mn}$. Then, it outputs $\sim (\sim\psi_1 \sqcap \cdots \sqcap \sim \psi_{8mn})$.\footnote{Note that $\sim (\sim\psi_1 \sqcap \cdots \sqcap \sim \psi_{8mn})$ is equivalent to $\psi_1\sqcup \cdots\sqcup \psi_{8mn}$.} Obviously, $\cM$ runs in polynomial time. Note also that the output formula uses $8mn(n+1)+1=O(mn^2)$ variables. Recall that on input $\varphi$ with $n$ variables, the reduction in Theorem~\ref{theo:valiant-vazirani} outputs a formula $\psi$ such that the following holds. \begin{itemize} \item If $\varphi \in \sat$, then $\prarg{\psi \in\usat}\geq 1/(8n)$. \item If $\varphi \notin \sat$, then $\prarg{\psi \in\sat}=0$. \end{itemize} Note the following. \begin{itemize} \item If $\psi \notin \paritysat$, then $\psi \notin \usat$. Thus, $\prarg {\psi\notin \paritysat} \leq \prarg {\psi\notin \usat}$. \item $\bigsqcup_{i=1}^{8mn} \psi_i \in\paritysat$ if and only if one of $\psi_i \in \paritysat$. \end{itemize} Thus, on input $\varphi$, the output $\bigsqcup_{i=1}^{8mn} \psi_i$ satisfies the following. \begin{itemize} \item If $\varphi \notin \sat$, then none of the $\psi_i$ is satisfiable. Thus, $\bigsqcup_{i=1}^{8mn} \psi_i \notin \paritysat$. Therefore, \begin{eqnarray*} \prargbig{ \bigsqcup_{i=1}^{8mn} \psi_i \ \in\ \paritysat } & = & 0 \end{eqnarray*} \item If $\varphi \in \sat$, the following holds. \begin{eqnarray*} \prargbig {\bigsqcup_{i=1}^{8mn} \psi_i \notin \paritysat} & = & \prod_{i=1}^{8mn} \prarg{\psi_i \notin \paritysat} \ \leq\ \Big(1-\frac{1}{8n}\Big)^{8mn} \ \leq \ (1/e)^{m} \ \leq \ (1/2)^{m} \end{eqnarray*} Therefore, $\prarg{\bigsqcup_{i=1}^{8mn} \psi_i \in \paritysat} \geq 1-(1/2)^m$. \end{itemize} This completes the proof of Lemma~\ref{lem:sat-to-paritysat}. \end{proof} \begin{lemma} \label{lem:unsat-to-paritysat} {\bf (Reduction from $\overline{\sat}$ to $\paritysat$)} There is a polynomial time PTM $\cM$ that on input formula $\varphi$ and a positive integer $m$ (in unary), outputs a formula, denoted by $\cM(\varphi,m)$, such that the following holds. \begin{itemize} \item If $\varphi \in \overline{\sat}$, then $\prarg {\cM(\varphi,m)\in\paritysat} =1$. \item If $\varphi\notin \overline{\sat}$, then $\prarg {\cM(\varphi,m)\in \paritysat} \leq (1/2)^m$. \end{itemize} \end{lemma} \begin{proof} The PTM $\cM$ works as follows. On input $\varphi$ and $m$, it runs the reduction in Lemma~\ref{lem:sat-to-paritysat} to obtain a formula $\psi$, and then outputs $\sim \psi$. If $\varphi \in \overline{\sat}$, then $\prarg {\psi \notin \paritysat} = 1$, and hence, $\prarg{\sim\psi \in \paritysat}=1$. If $\varphi \notin \overline{\sat}$, then $\prarg {\sim \psi \in \paritysat} = \prarg {\psi \notin \paritysat} \leq (1/2)^m$. \end{proof} Combining Lemmas~\ref{lem:sat-to-paritysat} and~\ref{lem:unsat-to-paritysat} and Cook-Levin reduction, we have the following. \begin{theorem} \label{theo:np-conp-to-paritysat} {\bf (Reductions from languages in $\npt\cup\conpt$ to $\paritysat$)} For every language $L\in \npt\cup\conpt$, there is a polynomial time PTM $\cM$ that on input word $w$ and a number $m$ (in unary), outputs a formula $\cM(w,m)$ such that the following holds. \begin{itemize} \item If $w\in L$, then $\prarg {\cM(w,m)\in\paritysat} \geq 1-(1/2)^m$. \item If $w\notin L$, then $\prarg {\cM(w,m)\in \paritysat} \leq (1/2)^m$. \end{itemize} \end{theorem} \section{Probabilistic reductions from languages in $\pht$ to $\paritysat$} In this section we will show how to extend Theorem~\ref{theo:np-conp-to-paritysat} to all languages in $\pht$. We need some terminology and notations. We write $\vx$, $\vy$ or $\vz$ to denote a sequence of variables, and the length is denoted by $|\vx|$, $|\vy|$ or $|\vz|$, respectively. Recall that a QBF is formula of the form: $Q_1\vz_1\cdots Q_k\vz_k\quad \phi$ where each $Q_i \in \{\forall,\exists\}$ and $Q_i \neq Q_{i+1}$, each $\vz_i$ is a vector of variables and $\phi$ is a formula that uses variables $\vz_1,\ldots,\vz_k$. Note that all variables used in $\psi$ are ``quantified.'' \paragraph*{QBF with free variables.} A {\em QBF with free variables} is a QBF formula that has variables that are not quantified, i.e., of the form: \begin{eqnarray*} \varphi & \defeq & Q_1\vz_1\cdots Q_k\vz_k\quad \phi \end{eqnarray*} where $\phi$ uses some variables $\vy$ that are ``free,'' i.e., not quantified by any quantifiers, in addition to the variables $\vz_1,\ldots,\vz_k$. In this case, we write $\varphi(\vy)$ to indicate that $\vy$ are free. For example, in the formula $\forall x \exists z (x\vee y \vee z)$, variables $x,z$ are quantified, but variable $y$ is free. We usually denote an assignment that assigns variables in $\vy$ as a string $\va \in \{0,1\}^n$ with the same length as $\vy$. For a QBF $\varphi(\vy)$ with free variable $\vy$ and $\va$ be an assignment on $\vy$, we write $\varphi(\va)$ to denote the QBF (without free variables) obtained by substituting every variable in $\vy$ according to $\va$. In the following the term ``QBF'' means a QBF which may or may not contain free variables. A {\em $k$-QBF} is a QBF in which there are $k$ alternating quantifiers, i.e., $Q_1\vz_1\cdots Q_k\vz_k\ \psi$, where each $Q_i\neq Q_{i+1}$. \paragraph*{The operations $\sim$, $\sqcap$ and $\sqcup$ with formulas with ``free'' variables.} In the following we will deal with boolean formulas $\varphi$ with ``free'' variables. Intuitively, free variables in a boolean formula are variables that cannot be renamed. We write $\varphi(\vy)$ to indicate that $\vy$ are the free variables in $\varphi$. \begin{itemize} \item $\sim \varphi(\vy)$ is defined as before and the resulting formula $\sim(\varphi(\vy))$ also have free variables $\vy$. \item For $\varphi(\vy)$ and $\phi(\vy)$, we rename the variables so that $\vy$ are the only common variables in $\varphi$ and $\phi$ and define $\varphi(\vy)\sqcap\phi(\vy) \ \defeq \ \varphi(\vy)\wedge\phi(\vy)$ with free variables $\vy$. \item For $\varphi(\vy)$ and $\phi(\vy)$, we define $\varphi(\vy)\sqcup\phi(\vy) \ \defeq \ \sim(\sim\varphi(\vy) \ \sqcap \ \sim\phi(\vy))$ with free variables $\vy$. \end{itemize} \begin{lemma} \label{lem:sigmasat-pisat-paritysat} {\bf (Reductions from $\sigmasat{k}$ and $\pisat {k}$ to $\paritysat$)} For every $k\geq 1$, there is a probabilistic polynomial time algorithm $\cM$ that on input a $k$-QBF $\varphi(\vy)$ and a positive integer $m$ (in unary), outputs a formula $\psi(\vy)$ such that \begin{eqnarray*} \prarg {\psi(\vy) \ \text{is ``correct''}} & \geq & 1-(1/2)^m \end{eqnarray*} Here we define a formula $\psi(\vy)$ to be ``correct'' when $\varphi(\va)$ is a true QBF if and only if $\psi(\va)\in\paritysat$, for every assignment $\va$ on $\vy$. \end{lemma} \begin{proof} The proof is by induction on $k$. The base case $k=1$ is similar to Lemmas~\ref{lem:sat-to-paritysat} and~\ref{lem:unsat-to-paritysat}. On input $1$-QBF $\varphi(\vy)$ and integer $m$, the algorithm $\cM$ works as follows. \begin{itemize} \item If $\varphi(\vy)$ is of the form $\exists\vx\ \psi(\vx,\vy)$, where $\vx$ contains $n$ variables, do the following. For each $i=1,\ldots,8mn$, construct formula $\alpha_i(\vy)$ as follows. \begin{itemize} \item Randomly choose $k \in \{2,\ldots,n+1\}$. \item Randomly choose a hash function $h\in \cH_{n,k}$, where $\cH_{n,k}$ is pair-wise independent. \item Let $\alpha_i(\vy)$ denote the formula $\psi(\vx,\vy) \wedge (h(\vx)=0)$. \end{itemize} Then, output the formula $\psi(\vy)$ where $\psi(\vy)$ is the formula $\bigsqcup_{i=1}^{8mn} \alpha_i(\vy)$. \item If $\varphi(\vy)$ is of the form $\forall\vx\ \psi(\vx,\vy)$, where $\vx$ contains $n$ variables, do the following For each $i=1,\ldots,8mn$, construct formula $\alpha_i(\vy)$ as follows. \begin{itemize} \item Randomly choose $k \in \{2,\ldots,n+1\}$. \item Randomly choose a hash function $h\in \cH_{n,k}$, where $\cH_{n,k}$ is pair-wise independent. \item Let $\alpha_i(\vy)$ denote the formula $\neg\psi(\vx,\vy) \wedge (h(\vx)=0)$. \end{itemize} Then, output the formula $\psi(\vy)$, where $\psi(\vy)$ is the formula $\sim \bigsqcup_{i=1}^{8mn}\alpha_i(\vy)$. \end{itemize} The proof that $\prarg {\psi(\vy) \ \text{is correct}}\geq 1-(1/2)^m$ is similar to Lemmas~\ref{lem:sat-to-paritysat} and~\ref{lem:unsat-to-paritysat}. For the induction hypothesis, we assume Lemma~\ref{lem:sigmasat-pisat-paritysat} holds for $k$, i.e., there is a probabilistic algorithm $\cM_0$ that on input a $k$-QBF $\varphi(\vy)$ and a positive integer $m$ (in unary), outputs a formula $\psi(\vy)$ such that $\prarg {\psi(\vy) \ \text{is correct}}\geq 1-(1/2)^m$. For the induction step, on input $(k+1)$-QBF $\varphi(\vy)$ and $m$, the algorithm $\cM$ works as follows. \begin{itemize} \item $\varphi(\vy)$ is of the form $\exists\vx\ \phi(\vx,\vy)$, where $\vx$ contains $n$ variables. For each $i=1,\ldots,8mn$, construct a formula $\alpha_i(\vy)$ as follows. \begin{itemize} \item Let $\beta_i(\vx,\vy)$ be the output of $\cM_0$ on input $\phi(\vx,\vy)$ and $(m+1)$. \item Randomly choose $k \in \{2,\ldots,n+1\}$. \item Randomly choose a hash function $h\in \cH_{n,k}$, where $\cH_{n,k}$ is pair-wise independent. \item Let $\alpha_i(\vy)$ denote the formula $\beta_i(\vx,\vy) \wedge (h(\vx)=0)$. \end{itemize} Then, output the formula $\psi(\vy)$ where $\psi(\vy)\defeq\bigsqcup_{i=1}^{8mn} \alpha_i(\vy)$. \item $\varphi(\vy)$ is of the form $\forall\vx\ \psi(\vx,\vy)$, where $\vx$ contains $n$ variables. For each $i=1,\ldots,8mn$, construct a formula $\alpha_i$, as follows. \begin{itemize} \item Let $\beta_i(\vx,\vy)$ be the output of $\cM_0$ on input $\neg\psi(\vx,\vy)$ and $(m+1)$. \item Randomly choose $k \in \{2,\ldots,n+1\}$. \item Randomly choose a hash function $h\in \cH_{n,k}$, where $\cH_{n,k}$ is pair-wise independent. \item Let $\alpha_i(\vy)$ be the formula $\beta_i(\vx,\vy) \wedge (h(\vx)=0)$. \end{itemize} Then, output the formula $\psi(\vy)$ where $\psi(\vy)\defeq\sim\bigsqcup_{i=1}^{8mn} \alpha_i(\vy)$. \end{itemize} We now calculate the probability of the event that $\psi(\vy)$ is correct. We first consider the case that $\varphi(\vy)$ is of the form $\exists\vx \phi(\vx,\vy)$. By the induction hypothesis, $\prarg {\beta_i(\vx,\vy) \ \text{is correct}} \geq 1-(1/2)^{m+1}$, for each $i=1,\ldots,8mn$. Note that $\beta_i(\vx,\vy)$ is correct, if for every assignment $\va$ and $\vb$ on $\vx$ and $\vy$, respectively, $\beta_{i}(\va,\vb)\in \paritysat$ if and only if $\phi(\va,\vb)$ is a true QBF. Assume that $\beta_i(\vx,\vy)$ is correct. Let $\vb:\vy\to\{0,1\}$ be such that $\varphi(\vb)$ is true QBF. Thus, for every assignment $\va:\vx\to\{0,1\}$, if $\varphi(\va,\vb)$ is true QBF, $\beta_i(\va,\vb) \in \paritysat$. Otherwise, $\beta_i(\va,\vb)\notin \paritysat$. So, we only need to consider all those assignments $\va$ such that $\phi_i(\va,\vb)$ is true, which by the induction hypothesis, is equivalent to saying that $\beta_i(\va,\vb)\in \paritysat$. By applying the same technique as in Lemma~\ref{lem:valiant-vazirani} on the set of $\va$ such that $\beta_i(\va,\vb)\in \paritysat$, we randomly ``choose'' the hash function $h$ such that there is unique assignment $\va$ such that $h(\va)=0$, and the probability that we choose such $h$ is $\geq 3/(16n)$. Thus, we have: \begin{eqnarray*} \prarg {\beta_i(\vx,\vy)\wedge h(\vx)=0 \ \text{is correct}\ \mid\ \beta_i(\vx,\vy) \ \text{is correct}} & \geq & \frac{3}{16n} \end{eqnarray*} Thus, \begin{eqnarray*} \prarg {\psi_i(\vx,\vy) \ \text{is correct}} \ = \ \prarg {\beta_i(\vx,\vy)\wedge h(\vx)=0 \ \text{is correct}} & \geq & \frac{3}{16n}\Big(1 - (1/2)^{m+1}\Big) \\ & \geq& \frac{1}{8n} \end{eqnarray*} where in the last inequality we assume that $m\geq 1$. Note also that if $\vb:\vy\to\{0,1\}$ is an assignment such that $\varphi(\vb)$ is false QBF, then $\beta_i(\va,\vb) \notin \paritysat$, for every assignment $\va$ (since $\beta_i(\vx,\vy)$ is a correct formula). Thus, for any choice of $h$, $\beta_i(\vx,\vb) \wedge h(\vx)=0 \notin \paritysat$. Finally, note that $\bigsqcup_{i=1}^{8mn} \alpha_i(\vy)$ is correct if and only if one of $\alpha_i(\vy)$ is correct. Therefore, \begin{eqnarray*} \prargbig {\bigsqcup_{i=1}^{8mn} \alpha_i(\vy) \ \text{is not correct}} & = & \prarg {\alpha_i(\vy) \ \text{is not correct, for each}\ i=1,\ldots,8mn} \\ & \leq & \Big(1- 1/(8n)\Big)^{8mn} \ \leq \ (1/2)^m \end{eqnarray*} The proof for the case where $\varphi(\vy)$ is of the form $\forall\vx\ \phi(\vx,\vy)$ is similar. \end{proof} Combining Lemma~\ref{lem:sigmasat-pisat-paritysat} and the fact that $\sigmasat{k}$ and $\pisat {k}$ are $\sigmap {k}$- and $\pip {k}$-complete, for each $k\geq 1$, we have the following theorem. \begin{theorem} \label{theo:ph-paritysat} {\bf (Reductions from languages in $\pht$ to $\paritysat$)} For every language $L \in \pht$, there is a probabilistic polynomial time algorithm $\cM$ that on input $w$, outputs a formula $\psi$ such that the following holds, where $n=|w|$. \begin{itemize} \item If $w \in L$, then $\prarg { \psi \in \paritysat} \geq 1-(1/2)^n$. \item If $w \notin L$, then $\prarg { \psi \in \paritysat} \leq (1/2)^n$. \end{itemize} \end{theorem} \appendix \section*{Appendix} \section{Pair-wise independent collection of hash functions} \label{app:hash} \begin{definition} \label{def:hash} For $n,k \geq 1$, let $\cH_{n,k}$ be a collection of functions from $\{0,1\}^n$ to $\{0,1\}^k$. We say that $\cH_{n,k}$ is {\em pair-wise independent}, if for every $x,x' \in \{0,1\}^n$ where $x\neq x'$ and for every $y,y'\in \{0,1\}^k$, the following holds. \begin{eqnarray*} \prdist {h \in \cH_{n,k}} {h(x)=y \ \wedge \ h(x')=y'} & = & 2^{-2k} \end{eqnarray*} \end{definition} In the following we show that $\cH_{n,k}$ exists. First, we show that $\cH_{n,n}$ exists. For every $n\geq 1$, for every $a,b \in \gf(2^n)$, define a function $h_{a,b}$ from $\{0,1\}^n$ to $\{0,1\}^n$ as follows.\footnote{$\gf(2^n)$ denotes a finite field with $2^n$ elements, where each element can be encoded as a 0-1 string of length $n$.} \begin{eqnarray*} h_{a,b}(x) & \defeq & xa+b \end{eqnarray*} \begin{theorem} \label{theo:hash-exists-a} The collection $\cH_{n,n} \defeq \{h_{a,b}: a,b \in \gf(2^n)\}$ is pair-wise independent. \end{theorem} We have another candidate for pair-wise independent collection. For every $n\geq 1$, for every $A \in \{0,1\}^{n\times n}$ and $b \in \{0,1\}^{n\times 1}$, define a function $h_{A,b}$ from $\{0,1\}^{n\times 1}$ to $\{0,1\}^{n\times 1}$ as follows.\footnote{$\{0,1\}^{n\times n}$ denotes the set of 0-1 matrices with $n$ rows and $n$ columns and $\{0,1\}^{n\times 1}$ denotes the set of 0-1 column vectors of $n$ rows. Here the addition $+$ and multiplication $\cdot$ are defined over $\bbZ_2$.} \begin{eqnarray*} h_{A,b}(x) &\defeq & A x+b \end{eqnarray*} \begin{theorem} \label{theo:hash-exists-b} The collection $\cH_{n,n} \defeq \{h_{A,b} : A \in \{0,1\}^{n\times n}\ \text{and}\ b \in \{0,1\}^{n\times 1}\}$ is pair-wise independent. \end{theorem} \begin{remark} Note that the existence of $\cH_{n,n}$ implies the existence of $\cH_{n,k}$. If $nk$, then we can use $\cH_{n,n}$ and reduce $n$ bit outputs to $k$ by truncating the last $(n-k)$ bits. \end{remark} \begin{lemma} \label{lem:valiant-vazirani} {\bf (Valiant and Vazirani, 1986)} Let $\cH_{n,k}$ be a pair-wise independent hash function collection. Let $S\subseteq \{0,1\}^n$ such that $2^{k-2}\leq |S|\leq 2^{k-1}$. Then, the following holds. \begin{eqnarray*} \prdist {h \in \cH_{n,k}} {\textup{there is a unique}\ x \in S\ \textup{such that}\ h(x)=0^k} & \geq & \frac{3}{16} \end{eqnarray*} \end{lemma} \begin{proof} Let $N$ denote the number of $x$'s such that $h(x)=0$, where $h$ is randomly chosen from $\cH_{n,k}$ (with uniform distribution). We will calculate $\prarg {N=1}$. Note that: \begin{eqnarray*} \prarg {N=1} & = & \prarg {N\geq 1} \quad - \quad \prarg {N\geq 2} \\ & = & \pr \Big[\ \bigcup_{x\in S} \cE_x\ \Big] \quad - \quad \pr \Big[\ \bigcup_{x,x'\in S \ \text{and}\ x\neq x'} \cE_{x}\cap \cE_{x'}\ \Big] \end{eqnarray*} where $\cE_x$ denotes the event that $h(x)=0$. In the following, we let $p = 2^{-k}$. Since $\cH_{n,k}$ is pairwise independent, $\prarg {\cE_x}=p$ and $\prarg {\cE_x \cap \cE_{x'}}=p^2$, whenever $x\neq x'$. By the inclusion-exclusion principle, we have: \begin{eqnarray*} \pr \Big[\ \bigcup_{x\in S} \cE_x\ \Big] & \geq & \sum_{x\in S} \prarg{\cE_x} \quad - \quad \ \sum_{x,x'\in S \ \text{and}\ x\neq x'} \prarg {\cE_{x}\cap \cE_{x'}} \ = \ |S|p \ - \ {|S| \choose 2}\cdot p^2 \end{eqnarray*} By union bound, we have: \begin{eqnarray*} \pr \Big[\ \bigcup_{x,x'\in S \ \text{and}\ x\neq x'} \cE_{x}\cap \cE_{x'}\ \Big] & \leq & \sum_{x,x'\in S \ \text{and}\ x\neq x'} \prarg{\cE_{x}\cap\cE_{x'}} \ \leq \ {|S| \choose 2}\cdot p^2 \end{eqnarray*} Combining both, we have: \begin{eqnarray*} \prarg{N=1} \ = \ \prarg{N\geq 1} - \prarg{N\geq 2} & \geq & |S|p\ - \ |S|^2p^2 \end{eqnarray*} Since $1/4 \leq |S|p \leq 1/2$, a straightforward calculation shows that $|S|p - |S|^2p^2 \geq 3/16$. \end{proof} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% END OF DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%