\documentclass[letterpaper]{article}
\usepackage{amsmath,amssymb,verbatim}
% Note: order of packages is important
\usepackage[pdftex,letterpaper=true]{hyperref}
\hypersetup{pdfpagelayout=SinglePage,pdfstartview=FitV,
pdfpagemode=None,pdftitle=CSCI6220/4030 HW4,
pdfauthor=Alex Gittens}
\usepackage[letterpaper,height=8.8in]{geometry}
\usepackage{algorithm}
\usepackage{graphicx}
\usepackage{enumitem}
\usepackage[noend]{algpseudocode}
% make the option "empty" to get rid of page numbers
%\pagestyle{empty}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\E}{\ensuremath{\mathbb{E}}}
\newcommand{\Prob}{\ensuremath{\mathbb{P}}}
\newcommand{\Var}{\ensuremath{\mathrm{Var}}}
\newcommand{\e}{\ensuremath{\mathrm{e}}}
\def\matA{\mathbf{A}}
\def\matB{\mathbf{B}}
\def\matT{\mathbf{T}}
\def\matX{\mathbf{X}}
\def\vecx{\mathbf{x}}
\def\vecr{\mathbf{r}}
\DeclareMathOperator{\Div}{div}
\DeclareMathOperator{\median}{median}
\makeatletter
\def\pairmod#1#2{#1\mkern3mu{\operator@font mod}\mkern3mu #2}
\makeatother
\begin{document}
\begin{center}
\Large{CSCI 6220/4030: Homework 5}
\end{center}
Assigned Tuesday November 13 2017. Due at beginning of class Monday November 26 2017.
Remember to typeset your submission, and label it with your name. Please start early so you have ample time to see me during office hours.
Provide mathematically convincing arguments for the following problems. Ask me if you are unclear whether your arguments
are acceptable.
\begin{enumerate}[label=\arabic*.]
\item Two rooted trees $T_1$ and $T_2$ are said to be isomorphic if there exists a one-to-one mapping $f$ from the vertices of $T_1$ to those of $T_2$ satisfying the
following condition: for each internal vertex $v$ of $T_1$ with the children $v_1, \ldots, v_k$, the vertex $f(v)$ has as children exactly the vertices $f(v_1),\ldots,f(v_k)$.
Observe that no ordering is assumed on the children of any internal vertex. Devise an efficient randomized algorithm for testing the isomorphism of rooted trees using the
Schwarzt-Zippel theorm, and analyze its cost and probability of success. Hint: associate a polynomial $P_v$ with each vertex $v$ in a tree $T$. The polynomials are defined recursively, with the base
case being that the leaf vertices all have $P=x_0$. An internal vertex $v$ of height $h$ with the children $v_1, \ldots, v_k$ has its polynomial defined to be $(x_h - P_{v_1})\cdots(x_h - P_{v_k})$.
Note that there is one indeterminate $x_h$ associated with each level $h$ in the tree.
%
% \item Given a boolean formula in CNF form $F(X_1, \ldots, X_n) = C_1
% \wedge \ldots \wedge C_m$, where the $C_i$ are disjunctive clauses in
% the Boolean variables $X_1, \ldots, X_n$, consider the problem of determining
% whether this formula is satisfiable, i.e., whether there exist boolean assignments to the variables which makes $F$ yield TRUE.
%
% Here is a natural scheme for converting the satisfiability problem into
% a polynomial equality problem: given a clause $C_i = L_{i_1} \vee
% \ldots \vee L_{i_k}$ replace any positive literal $X_j$ by $(1-x_j)$ and any negative literal $\lnot X_j$ by $x_j$ to form a monomial $c_i$, then form the polynomial
% \[
% f(x_1, \ldots, x_n) = \sum_{i=1}^m c_i
% \]
% \emph{over the field $\mathbb{Z}_2$}.
% As an example, if $C_i = X_{i_1} \vee \lnot X_{i_2} \vee X_{i_3}$, then $c_i = (1- x_{i_1})x_{i_2}(1-x_{i_3}).$
% \begin{itemize}
% \item Argue that if an assignment $\matX$ makes $F$ TRUE, then the corresponding vector $\vecx \in \mathbb{Z}_2^n$ gives $f(\vecx) = 0.$
% \item Show that the converse is not true: $f(\vecx)$ can be zero even when $F(\matX)$ is FALSE.
% \item To mitigate this lack of equivalence, we use a variant of Freivald's technique: choose a random vector $\vecr = (r_1, \ldots, r_m)$ uniformly at random from $\mathbb{Z}_2^m$ and instead define $f$ to be
% \[
% f(x_1, \ldots, x_n) = \sum_{i=1}^m r_i c_i.
% \]
% Argue that if $F(\matX)$ is TRUE, then $f(\vecx) = 0$, and if $F(\matX)$ is FALSE, then $\Prob[f(\vecx) = 0] = \frac{1}{2}.$
% \item Use the prior observation to describe an algorithm for testing whether $F$ is satisfiable that has failure probability
% \end{itemize}
\item Consider two computers, each containing $n$ bit strings of length $n$. It can be shown that any deterministic algorithm for determining whether these sets have a non-empty intersection requires $O(n^2)$ bits to be
communicated between the computers. Design a Las Vegas algorithm for answering this problem that communicates $O(n \log n)$ bits in expectation \emph{when the sets do not intersect}.
% \item {[{\bf Required only for CSCI 6220}]} Two $n \times n$ matrices $\matA$ and $\matB$ are said to be similar if there exists a non-singular matrix $\matT$ such that $\matT \matA \matT^{-1} = \matB.$ Devise a
% randomized algorithm for testing the similarity of the matrices $\matA$ and $\matB$ \emph{over the field $\mathbb{Z}_2$}. Hint: view the entries in $\matT$ as a collection of variables, and from the definition of similarity, obtain a homogeneous set of linear equations
% that these variables must satisfy. Apply randomized techniques to determine whether there exists a solution of these equations that also yields a non-singular matrix $\matT.$
\end{enumerate}
\end{document}