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

\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\vol}{\mathop{\rm Vol}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\renewcommand{\vec}[1]{{\mathbf #1}}
%\input{dansmacs}

\begin{document}

\noindent {\large Essential Coding Theory \hfill 
Madhu Sudan\\[-.1in]
6.896 \hfill  \mbox{}\\[-.1in]
Due:  Wednesday, September 11, 2002\hfill \mbox{}\\[.4in]}
{\LARGE \centering Problem Set 1 \\[.4in] \par}

\section*{Instructions}
\begin{description}
\item[References:]
In general, try not to run to reference material to answer
questions. Try to think about the problem to see if you can
solve it without consulting any external sources. If this fails,
you may look up any reference material.
\item[Collaboration:]
Collaboration is allowed, but limit yourselves to 
groups of size at most four. 
\item[Writeup:]
You must write the solutions in latex, by yourselves. 
Cite all references and collaborators. 
Explain why you needed to consult any of the references,
if you did consult any.
\end{description}

\section*{Problems}

\begin{enumerate}
\item {\sf (Linear Algebra Review):}  {\bf (Need not be turned in.)}
\begin{enumerate}
\item Given a $k \times n$ matrix 
$G$ with 0/1 entries, of rank $k$ over $\Z_2$, 
generating a linear code 
$C = \{\vec x \cdot G | \vec x\}$,
show that there exists an $n \times m$ matrix $H$, (henceforth
referred to as the parity check matrix), such that $C = 
\{\vec y | \vec y H = \vec 0\}$.  What is the relationship
between $m$, $n$ and $k$ above?
\item Give an efficient algorithm to compute such an $H$, given
$G$, and vice versa.
\item Give an explicit description of the generator matrix
of a Hamming code of block length $2^{\ell}-1$.
\end{enumerate}
\item {\sf (Binary Hamming code \& bound):}
\begin{enumerate}
\item
What is the rate of the Hamming code of block length $2^\ell-1$?
\item 
Show that if $C$ is a $t$-error-correcting code in $\{0,1\}^n$,
then $|C| \leq 2^n/\vol(n,t)$, where $\vol(n,t) = \sum_{i=0}^t 
\binom{n}i$.
\item Conclude that the Hamming codes of Part (a) are optimal
in their performance.
\end{enumerate}
\item (Extra Credit Question) For general $q$, give the best
construction you can of a $q$-ary code of minimum distance $3$.
\item {\sf (Pairwise independent spaces):}
\begin{enumerate}
\item Let $H$ be the $(2^{\ell} - 1) \times \ell$ parity check 
matrix of a binary Hamming code. Show that the collection of
column vectors $\{H \vec x^T | \vec x \in \{0,1\}^\ell\}$ forms
a pairwise independent space.
\item (Extra Credit Question) Show that any pairwise independent
space on $n$ bits must contain at least $n+1$ points.
\end{enumerate}

\item 
A Directed Cut (DiCut) in a directed graph $G = (V,E)$ is an ordered
partition $(S,\overline{S})$ of $V$. The size of the DiCut is the
number of edges $(u,v) \in E$ with $u \in S$ and $v \in \overline{S}$.
\begin{enumerate}
\item Show that every graph has a DiCut of size at least $|E|/4$.
\item Give a deterministic polynomial time algorithm to find
such a DiCut in a given graph.
\end{enumerate}
(There are two natural solutions to this problem - one that involves
pairwise independence and one that doesn't. Guess which one I want.)

\item {\sf The Hat Problem:}
\begin{enumerate}
\item Lets say that a directed graph $G$ is a subgraph of the
$n$-dimensional hypercube if its vertex set is $\{0,1\}^n$
and if $u \to v$ is an edge in $G$, then $u$ and $v$ differ in
at most one coordinate. Let $K(G)$ be the number of vertices
of $G$ with in-degree at least one, and out-degree zero.
Show that the probability of winning the hat problem equals
the maximum, over directed subgraphs $G$ of the $n$-dimensional
hypercube, of $K(G)/2^n$.
\item Using the fact that the out-degree of any vertex is at most
$n$, show that $K(G)/2^n$ is at most $\frac{n}{n+1}$ for any 
directed subgraph $G$ of the $n$-dimensional hypercube.
\item Show that if $n = 2^{\ell} -1$, then there exists a directed
subgraph $G$ of the $n$-dimensional hypercube with $K(G)/2^n = 
\frac{n}{n+1}$. (This is where the Hamming code comes in.)
\end{enumerate}
\end{enumerate}
\end{document}