
\documentclass[10pt]{article}
\usepackage{amsfonts,fullpage,amsmath}
\usepackage{hyperref}

%\usepackage{epsfig}

\begin{document}
\input{preamble.tex}
\newcommand{\group}[1]{\left\langle #1 \right\rangle}
\newcommand{\tgroup}[1]{\left| #1 \right\rangle}


\lecture{1}{Feb 4, 2015}{Madhu Sudan}{Itay Berman}

%%%% body goes in here %%%%

\section{Administrative Topics}
\begin{itemize}


\item Website: \url{http://people.csail.mit.edu/madhu/ST15/}.
\item Mailling list -- if you are not in it, please email Madhu with your details.
\end{itemize}


\subsection{Responsibilities}
\begin{enumerate}
\item Scribe: each student in the course (registered, listener or attending just for fun) must scribe at least one lecture. Please sign up for dates to scribe (see instructions in the course website).

\item Project: will mainly include reading and presenting a new topic to the class. A written report is also required, but no new results are expected.

\item Participation: please participate in class.

\item Problem Sets: maybe will be, and if so then maybe be submitted.
\end{enumerate}

\section{Motivating Example --- Factoring Polynomials \cite{ArLRS92}}
Consider the following question: Given $p_1(x),p_2(x)\in \F[x]$ (where $\F[x]$ is the polynomial ring in formal variable $x$ over the field $\F$, i.e., the set of polynomials in $x$ whose coefficients are elements of $\F$) with $deg(p_1),deg(p_2) < n$ and the sets $\set{p_1(\alpha_1),p_2(\alpha_1)}, \set{p_1(\alpha_2),p_2(\alpha_2)}, \ldots, \set{p_1(\alpha_{10n}),p_2(\alpha_{10n})}$, where $\set{\alpha_i}_{i=1}^{10n}$ are distinct elements in $\F$, can you compute $p_1$ and $p_2$?

If we could have known in the $i$'th set which element corespondents to evaluation of which polynomial on $\alpha_i$, we can simply interpolate and get both $p_1$ and $p_2$. We can, however, compute $A = p_1 + p_2$ and $B= p_1\cdot p_2$ without knowing this correspondence. We cen now define the bivariate polynomial $q\in\F[x,y]$ as
\begin{align*}
q(x,y) \eqdef (y-p_1(x))\cdot(y-p_2(x)) = y^2 - A(x)\cdot y + B(x).
\end{align*}
Note that the roots of $q$ with respect to $y$ are exactly $p_1$ and $p_1$, so by the quadratic formula we can write
\begin{align*} 
y = \frac{A \pm \sqrt{A^2 - 4B}}{2}.
\end{align*}
But can we really use the quadratic formula for bivariate polynomials as we did? Can we divide by $2$ in the field? What does square root means? It turns out that we can answer the above questions, and to show that this approach works.

What if we have more polynomials, say $p_1,p_2,\ldots,p_{10}$? We can define again
\begin{align*}
q(x,y) \eqdef (y-p_1(x))\cdot (y-p_2(x)) \cdot \ldots \cdot  (y-p_{10}(x)) = y^{10} - A_1(x)\cdot y^9 + A_2(x)\cdot y^8 + \cdots + A_{10}(x).
\end{align*}
Now, $q$ is no longer quadratic in $y$, and we don't have a formula to use to factor it. Can we solve this problem? Can we do so efficiently? The above questions and more will be addressed in this course.

\section{Course Topics}
\subsection{Primer on Algebra}
Some examples:
\begin{enumerate}
\item degree $n$ polynomials has at most $n$ roots (this theorem is used everywhere in CS).
\item $(x+y)^p = x^p + y^p$ over fields with characters $p$.
\item spare polynomial with many roots: $\prod_{\alpha\in\F_q}(x-\alpha) = x^q - x$, where $\abs{\F_q} = q$.
\end{enumerate}

\subsection{Algorithms for Polynomials}
\begin{enumerate}
\item addition, multiplication, division, GCD.
\item Factorization:
\begin{enumerate}
\item univariate polynomials factorization over finite fields.
\item univariate polynomials factorization over rationals.
\item multivariate polynomials factorization.
\item (root finding over real polynomials.)
\end{enumerate}
We'll see that the relation between the above algorithms relies on a connection between $Z$ to $\F[x]$.

\item primality testing (much more algebra than number theory).
\item solving systems of polynomial equations (NP-hard): Grobner basis, ideal membership.
\end{enumerate}

\subsection{Complexity}
\begin{enumerate}
\item Models: circuits and formulas.
\item Determinant (easy) vs. Permanent (hard).
\item $P=NC$ (in the algebraic sense), or small circuits are equivalent to small depth.
\item Lower bounds.
\item Polynomial identity testing: we know how to do it with randomized algorithms, but not deterministic ones (how to prove a polynomial is the zero polynomial?)
\end{enumerate}

\section{Membership in Permutation Group}
You are given a cube and a set of legal moves. Can you transform the cube, using only legal moves, to some specific configuration? This question is exactly the problem of membership in permutation group.

Let $[n]\eqdef \set{1,\ldots,n}$, let $S_n$ denote the set of permutations from $[n]$ to $[n]$, let $e\in S_n$ denote the identity permutation, and for $f,g\in S_n$ let $(g\cdot f)(i)\eqdef g(f(i))$. For $T\subseteq S_n$, let $\group{T}$ denote the group generated by $T$ with respect to operation `$\cdot$'.

\begin{definition}[Permutation Group Membership]
Given $T\subseteq S_n$ such that $T=\set{t_1,t_2,\ldots,t_k}$ and $\sigma \in S_n$, decide if $\sigma\in\group{T}$ (in time \poly(n,k)).
\end{definition}

We we'll see how to implement the following natural strategy. Our goal is to transfer the identity permutation $e$ (which always belongs to $\group{T}$) to $\sigma$ using only moves from $T$. Namely, we want to find $T_1,T_2,\ldots,T_r \in T$ such that $e \cdot T_1 \cdot \ldots \cdot T_r \equiv \sigma$ with the following restrictions. Each $T_i$ fixes the first $i-1$ elements of $[n]$ (i.e., $T_i(j) = j$ for $j<i$) and transfer $\sigma^{-1}(i)$ to $i$ (i.e., $T_i(\sigma^{-1}(i))= i$). What guarantees that such $T_i$'s exists? If $T_1$ does not exists, then $\sigma \notin \group{T}$ (since $\sigma$ itself meets $T_1$'s requirements). If $T_1,\ldots,T_i$ exist, then if $T_{i+1}$ does not exists, it follows that $\sigma\notin \group{T}$ (since $\sigma\cdot T^{-1}_1 \cdot \ldots \cdot T^{-1}_{i}$ meets $T_{i+1}$'s requirements).

So, if we can efficiently find these $T_i$'s, or determined that there are none, we can solve the permutation group membership problem. To do so we use the following generators.
\begin{definition}
A permutation $\pi\in S_n$ has $type(\pi)=i$ if $\pi(j)=j$ for every $j\in [i-1]$ and $\pi(i)\neq i$.
\end{definition}

\begin{definition}
A set $S\subseteq \group{T}$ is  \emph{Strong Generating Set for $\group{T}$} if 
\begin{align*}
\forall i < j \colon \left(\exists \pi\in\group{T} \textit{ s.t. } type(\pi)=i \land \pi(j)=i \right) \implies \exists! \tau\in S \textit{ s.t. } type(\tau)=i \land \tau(j)=i
\end{align*}
\end{definition}
Note that the size of every strong generating set is at most $\binom{n}{2}$.

Given a strong generating set for $\group{T}$, we can use the above approach to find these $T_i$'s, or to determined that $\sigma\notin \group{T}$. It is left to show how to find such strong generating set. For $S\subset S_n$ let $\tgroup{S} = \set{\pi_r\cdot\pi_{r-1}\cdot \ldots\cdot \pi_1 \colon \pi_i \in S \land type(\pi_i) > type(\pi_{i-1})}$ and for $\pi\notin \tgroup{S}$ let $FinalEle(\pi,S)$ denote the final permutation generated by taking the previous permutation, starting with $\pi$, and compose it with a permutation from $S$ such that the resulting permutation has larger type than the previous permutation.

\vspace{.5cm}
\noindent\textbf{Sims' Algorithm} ($T$)\\
$S \leftarrow \emptyset$\\
\WHILE  \, $\exists \sigma,\tau\in S\cup T$ s.t. $\sigma \cdot T \notin \tgroup{S}$:

$S \leftarrow FinalEle(\sigma\cdot \tau,S) \cup S$.

\vspace{.5cm}
At the end of Sims' algorithm, the set $S$ is strong generating set for $\group{T}$ (we did not show this in class).





\bibliography{biblo}
\bibliographystyle{plain}

\end{document}
