\documentclass{article}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\ind}[1]{\mathbf{1}[#1]}
\newcommand{\inset}[1]{\left\{#1\right\}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\spn}{\mathrm{span}}
\newcommand{\Vol}{\mathrm{Vol}}
\newcommand{\wt}{\mathrm{wt}}
\newcommand{\tr}{\mathrm{Tr}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\polylog}{\mathrm{polylog}}
\usepackage{fullpage,graphicx}
\usepackage{amsmath,amsfonts,amsthm,amssymb,multirow}
\usepackage{algorithmic,comment,url,enumerate}
\usepackage{tikz}
\usepackage{framed}
\usepackage{enumitem}
\setenumerate[1]{label=\thesection.\arabic*.}
\usetikzlibrary{decorations.pathreplacing, shapes}
\usepackage[ruled,vlined,commentsnumbered,titlenotnumbered]{algorithm2e}
\definecolor{shadecolor}{gray}{0.95}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}


\begin{document}
\noindent CS250/EE387: Error Correcting Codes \hfill  Winter 2025\\
\textbf{Problem Set 3} \\
\textbf{Due:} by 11:59pm on Friday February 21, 2025, on Gradescope.\\
\hrule

\begin{shaded}

\textbf{Team Members: }

\textbf{(Optional) Awesome Team Name: }

\end{shaded}


\vspace{.5cm}
\noindent \textbf{Instructions:} 
\begin{itemize}
\item Please complete all problems in Section 1.  
\item Try to complete 3 of the problems in Section 2.  You are welcome to do more than 3, but please indicate which 3  you want graded.  
\item No problems in Section 3 are required, but they might be fun to think about (some might be open-ended).  
\item Problems are labeled with the class number after which you should be able to do them.  (This is to aid your time management since all HWs are posted up front).
\end{itemize}
\noindent \textbf{Guidelines/rules:}
\begin{itemize}
\item You are encouraged to work in groups (up to 3); each group should turn in one HW assignment.
\item Please refer to the collaboration policy on the course website.  
It is fine to use computational resources like Sage or Mathematica if you want to.
\end{itemize}
Typing up your solutions in \LaTeX \ is encouraged (but I don't type up my lecture notes, so I can't be too strict).  Legibility and complete sentences are required.  
\\
\hrule

\section*{Section 1} 
\setcounter{section}{1}
\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%

\item (4 pts, Class 10) Suppose that $q=2$.  Recall that the 
Johnson bound implies that there are codes of rate $R$ that are $(p,L)$-list-decodable (for reasonable $L$) as long as 
$$ R < 1 - H_2(2p(1-p)).$$
What is this, quantitatively, for $p = 2/5$?  How does this compare to the list-decoding capacity theorem?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


%%%%%%%%%%%%%%%%%%%%%%%5

 \item (8 pts, Class 10) Let $p = 1/8$.  At what rate $R$ can you (or rather, can we so far in this class) guarantee each of the following?  For each,
explain your answers.  (Also, please give your answers in the format ``$\approx 0.33$" rather than, say, ``$\sqrt{H_2^{-1}(1/2)}$.")
\begin{enumerate}
	\item There exists a family of binary codes of rate $R$ that can correct a $p$-fraction of adversarial errors?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item There exists a family of binary codes of rate $R$ that can \em efficiently \em correct a $p$-fraction of adversarial errors?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item There exists a family of binary codes of rate $R$ that can correct a $p$-fraction of \em random \em errors?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	\item There exists a family of binary codes of rate $R$ that can \em list-decode \em up to a $p$-fraction of adversarial errors?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}



\end{enumerate}
\section*{Section 2}
\setcounter{section}{2}
(Section 2 problems are worth 10 points each; please do at least 3 of them.)

\vspace{.5cm}
\noindent
\textcolor{red}{
\textbf{IMPORTANT:} In gradescope, please tag all problems you want feedback on.  However, if you tag more than 3,  write ``NOT FOR GRADING!!!!'' prominently at the top of all but 3 of them.  }

\vspace{.5cm}

\begin{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%5

\item (\textbf{MDS-like codes}, Class 4)  In this problem, we will consider a number-theoretic counterpart of Reed-Solomon codes.  Let $1 \leq k < n$ be integers and let $p_1 < p_2 < \cdots < p_n$ be $n$ distinct primes.  Let $K = \prod_{i=1}^k p_i$.  Let $\mathbb{Z}_M$ denote the integers modulo $M$ (that is, the set $\{0,1,\ldots, M-1\}$ with addition and multiplication mod $M$).  Consider the ``code'' defined by the encoding map $E: \ZZ_K \to \ZZ_{p_1} \times \ZZ_{p_2} \times \cdots \times \ZZ_{p_n}$ given by
\[ E(m) = (m \mod p_1, m \mod p_2, \ldots, m \mod p_n ). \]
That is, let $\cC \subseteq \ZZ_{p_1} \times \cdots \times \ZZ_{p_n}$ be defined as the image of $E$.
(Notice that $\cC$ is not a code under our definition since it has different alphabets for different symbols, which is why ``code'' above is in quotes.)

\begin{enumerate}
\item Suppose that $m, m' \in \ZZ_K$ are distinct messages.  
Let $A \subseteq [n]$ be the set of indices $i$ so that $m = m' \mod p_i$.
Prove that $\prod_{i\in A} p_i$ divides $m - m'$, where we treat $m$ and $m'$ as integers in $\{0,\ldots, K-1\}$.  

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Define the ``distance'' of the ``code'' above to be
\[ d = \min_{m \neq m' \in \ZZ_K} \sum_{i=1}^n\ind{ E(m)_i \neq E(m')_i }. \]
Use part (a) to show that the ``distance'' of $\cC$ is $d = n - k + 1$.  

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item (Open-ended, you'll get full points for anything reasonable).  Do you think this code counts as ``meeting the Singleton bound?'' Why or why not?  (Notice that this is not well-defined since we haven't defined ``rate'' or ``message length'' for a code where each symbol has a different alphabet, and because our definition of ``distance'' in the previous part might not be the only way to define ``distance'' in this setting.  Moreover, the ``correct'' version of the Singleton bound in this setting might be slightly different.)

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%

\item (\textbf{$(\ell,\ell)$-list-recoverability}, Class 4)
\begin{enumerate}
	\item Let $f,g \in \F_q[X]$ be polynomials of degree at most $k < (q-1)/2$.  Suppose for every $\alpha \in \F_q$, we are given the sets $\inset{ f(\alpha), g(\alpha) }$; these sets come labeled with $\alpha$, but we do not know which element of the set comes from $f$ and which comes from $g$.  Give an efficient (aka, polynomial in $q$) algorithm for recovering $f$ and $g$.

\textbf{NOTE:} Please do this from first principles (and/or from the second hint below), do not use the Guruswami-Sudan algorithm (which we may have seen in class by the time you get to this problem).  The solution to this problem is much easier than the GS algorithm. 

\underline{Hint 1:} Consider the polynomial $p(X,Y) = (Y - f(X))(Y - g(X))$.

\underline{Hint 2/supplementary resource:} You may use the following fact: if you have a polynomial $p(X,Y)$ as in Hint 1, you can factor it to find $f(X)$ and $g(X)$ in polynomial time.  In the special quadratic case above, it might be fun to figure out an algorithm to do this from scratch.  If you are curious to see how it's done for general bivariate polynomials, see Section 2 here: \url{http://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec10.pdf}.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


	\item Later in the course (or perhaps by now depending on when you do this PSET), we will see the following definition:
\begin{definition}\label{def:listrec}
	A code $\cC$ is \emph{$(\ell,L)$-list-recoverable} if for all collections of sets $S_1,\ldots, S_n \subset \Sigma$ so that $|S_i| \leq \ell$ for all $i$, there are at most $L$ codewords $c \in \cC$ so that $c_i \in S_i$ for all $i$.
\end{definition}

	In part (a), you saw that full-length RS codes (aka, RS codes over $\F_q$ with length $n=q$) of an appropriate dimension have the following property of a code $\cC \subseteq \Sigma^n$:
\begin{quote}
For any $c, c' \in \cC$, given the unordered sets $\{c_i, c'_i\}$ for $i = 1, \ldots, n$, it is possible to recover $c, c'$.
\end{quote}

	What is the relationship between this property and $(2,2)$-list-recoverability?  (That is, are they the same?  Is one stronger than the other?  Are they uncomparable?)


\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	
	\item Suppose that a family of MDS\footnote{Recall that an MDS (Maximum Distance Separable) code is a linear code that meets the Singleton bound; that is, the distance is $d = n -k +1$.} codes is $(\ell,\ell)$-list recoverable.  Show that the rate of the code satisfies $R \leq 1/\ell + o(1)$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item(\textbf{Efficient group testing algorithms}, Class 8) Let $\cC \subset \F_q^n$ be any code, and let $A \in \{0,1\}^{nq \times |\cC|}$ be the group testing matrix obtained by the Kautz-Singleton construction we saw in the lecture videos/notes.  (That is, the columns of $A$ are codewords of $\cC$ concatenated with the identity code).
\begin{enumerate}
	\item Suppose that $\cC$ is $(d,d)$-list-recoverable, as per Definition~\ref{def:listrec}, and suppose that $|\cC| > d$.  Show that $A$ can identify up to $d$ defective items.  

\textbf{NOTE:} For partial credit, (say, 8 out of the 10 points for this problem, assuming you do part (b)) you can prove the (easier) statement that $A$ can identify any set of \em exactly \em $d$ defectives.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

	
	\item Suppose that $\cC$ has a $(d,d)$-list-recovery algorithm that runs in time $\poly(n)$.  Give a sublinear-time algorithm (sublinear in $|\cC|$) for the corresponding group testing scheme.  (That is, given the outputs of the tests, give an algorithm to identify the $\leq d$ defective items in time $\poly(nq)$, where $nq$ is the number of tests in $A$; notice this is much less than $|\cC|$ which is the total number of items that were pooled.) 

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\item (\textbf{Codes which are good for random errors aren't \em terrible \em for worst-case errors}, Class 9)
Let $\cC \subset \{0,1\}^n$ be a code of rate $k/n$, with encoding and decoding algorithms $E:\{0,1\}^k \to \{0,1\}^n$ and $D:\{0,1\}^n \to \{0,1\}^k$.  Fix any constant $\gamma > 0$ and $p \in (0,1/2)$.  Suppose that $\cC$ has error probability at most $2^{-\gamma n}$ on the $BSC_p$ channel:
for all $x \in \{0,1\}^k$, 
\[ \mathbb{P}_{BSC_p} \inset{ D( BSC_p( E( x ) ) ) \neq x } \leq 2^{-\gamma n}. \]
Show that there is some constant $C_p$, which depends only on $p$, so that the relative distance of $\cC$ is at least $C_p \cdot \gamma$.  (Here, you may assume that $\gamma$ is a fixed constant, and that $n$ is sufficiently large in terms of $\gamma$).

\underline{Hint}: There is probably a correct solution that has lots of $H(p)$'s in it and a bunch of mucky algebra.  But there's also a correct solution that doesn't have any $H(p)$'s and no mucky algebra.

\underline{Second Hint}:  Suppose you have two codewords $c, c'$ that disagree on $\{1, \ldots, \delta n\}$.  Consider the set of vectors $y \in \{0,1\}^n$ that agree with $c$ on $\{1, \ldots, \delta n/ 2\}$ and agree with $c'$ on $\{ \delta n / 2 + 1, \ldots, \delta n\}$.  (And say that $\delta n$ is an even integer---you can assume this if you want).   What is the probability that $BSC_p(c)$ ends up in this set?  What about $BSC_p(c')$?

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\item (\textbf{Average-radius version of list-decoding}, Class 10)
	Consider the following Theorem.
\begin{theorem}\label{thmm}
Let $\cC \subset \mathbb{F}_2^n$ be a binary code, and fix a parameter $L$.  Then for any $\Lambda \subset \cC$ with $|\Lambda| = L$, 
\[ \min_{z \in \F_2^n} \frac{1}{L} \sum_{c \in \Lambda} \delta(c,z) \geq \frac{1}{2} \left( 1 - \sqrt{ 1 - \frac{2}{L^2}\sum_{c' \neq c'' \in \Lambda} \delta(c',c'') } \right).\] 
\end{theorem}
\begin{enumerate}
\item Show that Theorem~\ref{thmm} implies that:
\begin{quote}
Let $C$ be a binary code with relative distance $\delta$.  
For any $p < J_2(\delta)$, for sufficiently large $n$, $C$ is $(p, \poly(n))$-list-decodable.
\end{quote}
Note that this is similar to the version of the Johnson bound that we stated in the lecture videos/notes (for $q=2$).

\underline{Hint}: To try to parse the left-hand side, explain to yourself why $(p, L-1)$-list-decodability is the same thing as: for all sets $\Lambda \subseteq \cC$ with $|\Lambda| = L$,
\[ \min_{z \in \F_2^n} \max_{c \in \Lambda} \delta(c,z) \geq p. \]

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Let $\Phi \in (\pm 1)^{n \times 2^k}$ be the matrix whose columns are indexed by $c \in \cC$, so that $\Phi_{j,c} = (-1)^{c_j}$. 
Let $\ind{\Lambda}$ denote the indicator vector for a set $\Lambda$.   Relate the quantity on the left-hand-side of Theorem~\ref{thmm} 
to the $\ell_1$ norm of $\| \Phi \ind{\Lambda} \|_1$.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item 
Conclude that
\begin{align*}
L - \min_z \sum_{c \in \Lambda}  \delta(c, z) 
&\leq \frac{1}{2} \left( L + \frac{1}{\sqrt{n}} \left\| \Phi \ind{\Lambda}\right\|_2 \right),
\end{align*}

\underline{Hint:} The Cauchy-Schwarz Inequality is your friend.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\item Prove Theorem~\ref{thmm}.

\begin{shaded}
\textbf{SOLUTION:}
Your solution here!
\end{shaded}

\end{enumerate}

\end{enumerate}
\section*{Section 3}
\begin{enumerate}

\item In Section 2 we defined $(\ell,\ell)$-list-recoverability at you showed that any MDS code that is $(\ell,\ell)$-list-recoverable has rate at most $1/\ell$.   Can you show this for any \em linear \em code?  What about for any (possibly non-linear) code?

\begin{shaded}
\textbf{SOLUTION:}
Your thoughts here!
\end{shaded}


\item In class we proved one side of the list-decoding capacity theorem by looking at a completely random code.  
Recall that we proved the GV bound by looking at a random \em linear \em code.
Does the proof we saw for list-decoding work if you look at a random linear code?  Can you show that there exists a linear code that approaches list-decoding capacity?  Can you show that a random linear does with high probability?


\begin{shaded}
\textbf{SOLUTION:}
Your thoughts here!
\end{shaded}

\item The capacity on the BSC$_p$ is $1 - H(p)$, which is the same as list-decoding capacity.  Why are these the same?  Can you come up with a formal relationship between list-decoding and decoding on the BSC? 

\begin{shaded}
\textbf{SOLUTION:}
Your thoughts here!
\end{shaded}

\item Can you find a Reed-Solomon code (that is, a way of choosing evaluation points) that provably does \emph{not} approach list-decoding capacity?  Can you find a Reed-Solomon code that does?  (Or even prove that one exists?) 

\begin{shaded}
\textbf{SOLUTION:}
Your thoughts here!
\end{shaded}


\item In Section 2, we saw MDS-like codes based on the Chinese Remainder Theorem.  Can you adapt the Guruswami-Sudan algorithm (Class 11) to work for these codes? 

\begin{shaded}
\textbf{SOLUTION:}
Your thoughts here!
\end{shaded}

\end{enumerate}
\end{document}
