diff options
Diffstat (limited to 'ps4')
| -rw-r--r-- | ps4/main.tex | 136 |
1 files changed, 134 insertions, 2 deletions
diff --git a/ps4/main.tex b/ps4/main.tex index 7799f32..ecda8e0 100644 --- a/ps4/main.tex +++ b/ps4/main.tex @@ -24,6 +24,8 @@ \DeclareMathOperator{\E}{\mathbb{E}} +\DeclareMathOperator{\Enc}{\mathrm{Enc}} +\DeclareMathOperator{\Dec}{\mathrm{Dec}} \let\P\relax \DeclareMathOperator{\P}{\mathbb{P}} \DeclareMathOperator*{\argmin}{\arg\min} @@ -59,14 +61,144 @@ $|B(r,\delta)\cap \mathcal{C}|\leq L$. Hence: \end{displaymath} Furthermore, each code-word $c$ of $\mathcal{C}$ is counted several times in the sum: once for each $r\in B(c,\delta)$. But $B(c,\delta)$ is of size -$q^{\hat{n}H_q(\delta, \hat{n})}$. So each $c\in\mathcal{C}$ appears at most +$q^{\hat{n}H_q(\delta, \hat{n})}$, so each $c\in\mathcal{C}$ appears $q^{\hat{n}H_q(\delta, \hat{n})}$ times in the sum: \begin{displaymath} - |\mathcal{C}|q^{\hat{n}H_q(\delta, \hat{n})}\leq + |\mathcal{C}|q^{\hat{n}H_q(\delta, \hat{n})}= \sum_{r\in \Sigma^{\hat{n}}} |B(r,\delta)\cap\mathcal{C}| \end{displaymath} Putting the previous two equations together: $ |\mathcal{C}|q^{\hat{n}H_q(\delta, \hat{n})} \leq Lq^{\hat{n}}$. Taking the $\log$ both sides and reordering the terms (and using $\rho = \frac{\log |\mathcal{C}|}{\hat{n}\log q}$) concludes the proof. + +\section*{Problem 5.2} + +\paragraph{1.} For two different messages $m_1$ and $m_2$, $\Enc_1(m_1)$ and +$\Enc_1(m_2)$ differ on at least $\delta_1 n_1$ letters by definition of the +minimum distance of $\Enc_1$. For each one of those $\delta_1 n_1$ positions +where the letters differ, the images by $\Enc_2$ of the letters at this +position differ on at least $\delta_2 n_2$ letters by definition of the +minimum distance of $\Enc_2$. By summing over all such positions, we obtain +$\delta_1n_1\delta_2n_2$ positions where $\Enc(m_1)$ and $\Enc(m_2)$ differ. +This proves that the minimum distance of $\Enc$ is at least $\delta_1\delta_2$. + +\paragraph{2.} \emph{(Thanks Thomas for helping me late at night two days after +the homework was due!)} Let us consider a received word $r$, and a message $m$ +such that $d(\Enc(m), r)\leq (1-\eps_1l_2)\delta_2$. We can view $r$ as the +concatenation of $n_1$ blocks, each of size $n_2$. Denoting by $r_i$ the $i$th +block, I first note that the fraction of $i$s such that $d(r_i, +\Enc_2(\Enc_1(m)_i)$ is at most $(1-\eps_1l_2)$. Otherwise, by summing over $i$ +we would have $d(Enc(m), r)> (1-\eps_1l_2)\delta_2$, a contradiction. + +Hence, by $l_2$ list-decoding each of the blocks $r_i$, we obtain $n_1$ lists +of $l_2$ characters from $\Sigma_1$, such the $i$s such that the $i$th list +does not contain $\Enc_1(m)_i$ are a fraction at most $(1-\eps_1l_2)$. + +I now construct $l_2$ words $c_1,\dots, c_{l_2}$ such that $c_j$ is obtained by +taking the $j$th character in each of the $n_1$ lists of length $l_2$ obtained +by $l_2$ list-decoding in the previous paragraph. + +I claim that one of those words $c_j$ is such that $d(c_j, Enc_1(m))\leq +1-\eps_1$. Otherwise, by summing over $j$, and denoting by $f$ the fraction of +$i$s such that the $i$th list does not contain $\Enc_1(m)_i$: +\begin{align*} + (1-\eps_1)l_2&< \sum_{j=1}^{l_2} d(c_j, Enc_1(m)) + = \frac{1}{n_1}\sum_{i=1}^{n_1}\sum_{j=1}^{l_2} \left[(c_j)_i\neq + Enc_1(m)_i\right]\\ + &= fl_2 + (1-f)(l_2-1) = l_2 - 1 + f\leq l_2-1+(1-\eps_1l_2) + = (1-\eps_1)l_2 +\end{align*} +where the second equality was obtained by splitting the sum over $i$ depending +on whether or not $\Enc_1(m)_i$ belongs to the $i$th list, and the last +inequality was obtained by using the bound on $f$ found in the first paragraph +of this answer. Looking at the two extremal terms of the above computation, we +see a contradiction. + +Hence, one of the $c_j$ is such that $d(c_j, Enc_1(m))\leq +1-\eps_1$. By $l_1$-decoding all the $c_j$s, we obtain $l_2l_1$ words in +$\{1,\dots, N\}$ such that one of them is $m$ (since $\Enc_1$ is $l_2$ +list-decodable at distance $1-\eps_1$). This proves that $\Enc$ is $l_1l_2$ +list-decodable at distance $(1-\eps_1\l_2)\delta_2$. + +\paragraph{3.} We consider: +\begin{itemize} + \item $\Enc_1$: the Reed-Solomon code consisting of all polynomials of + degree $d = \frac{n}{m}-1$ over $\mathbb{F}_{2^m}$. + \item $\Enc_2$: the Hadamard code of all linear functions from + $\mathbb{F}_2^m$ to $\mathbb{F}_2$. +\end{itemize} +Since $\mathbb{F}_2^m$ can be identified with $\mathbb{F}_{2^m}$ these two +codes are compatible for concatenation. Both codes have block length $2^m$ so +the resulting block length after concatenation is $2^{2m}$. The bit length of +the code is $(d+1)m = n$ as requested. + +If we choose $m$ large enough such that $\frac{n}{m2^m}\leq \eps$, then the +minimum distance of the RS code is $1-\frac{n/m-1}{2^m}\geq +1-\frac{n/m}{2^m}\geq 1-\eps$. Hence, by \textbf{1.}, the minimum distance of +the concatenated code is at least $\frac{1}{2}(1-\eps)$ as requested. +Finally, if $\frac{n}{m2^m}\leq \eps$, the block length of the concatenated +code, $2^{2m}$, is $O(\frac{n^2}{\eps^2})$ as requested. + +Since $m = O(\log \frac{n}{\eps})$ and $m(d+1) = n$, it is clear that the code +is fully explicit. + +\section*{Problem 5.6} + +\paragraph{1.} I follow the hint by allowing the bivariate polynomial $Q$ in +the proof of Theorem 5.19 to have as many monomials as possible. More +precisely, we allow all monomials of degree $(d_1, d_2)$ such that: +\begin{displaymath} + d_1 + d\cdot d_2\leq \lfloor\eps q\rfloor \eqdef D +\end{displaymath} +and we will be fine as long as the number of monomials is strictly larger than +$q$ (to make sure we can find such a $Q$). Hence, all we have to do is count +the number of pairs $(d_1,d_2)$ such that $d_1 + d\cdot d_2\leq \eps q$ and +make sure that it is strictly larger than $q$. We see +that $d_2$ can be at most $A\eqdef\lfloor D/d\rfloor$ (in which case +$d_1$ has to be zero). If $d_2 = A - k$ for $k\in\{0,\dots, A\}$, then $d_1$ +can be as large as $D -kd$. Hence, the total number of monomials is: +\begin{displaymath} + N = \sum_{k=0}^A (D-kd + 1) = (D+1)(A+1) - \frac{d}{2} A(A+1) + = (A+1)\left(D+1-\frac{d}{2}A\right) +\end{displaymath} +For $\eps=\sqrt{2d/q}$, we have $A=\lfloor D/d\rfloor = \lfloor +\sqrt{2q/d}\rfloor$ and $D=\lfloor +\sqrt{2qd}\rfloor$. This leads to: +\begin{displaymath} + N > \sqrt{2q/d}\left(\sqrt{2qd} - \frac{d}{2}\sqrt{2q/d}\right) = q +\end{displaymath} +as desired. + +\section*{Problem 5.7} + +\paragraph{1.} Let us denote by $r\in\{0,1\}^{\hat{n}}$ the answers given by +the mean oracle trying to hide the secret from us. First observe that, denoting +by $[A]$ the Iverson bracket of event $A$ and $c_i = \Enc(s_i), i\in\{1,2\}$: +\begin{displaymath} + \hat{n}d(c_1, c_2) = \sum_{l=1}^{\hat{n}} [(c_1)_i\neq (c_2)_i] + = \sum_{i=1}^{\hat{n}}[(c_1)_i\neq r_i] + [(c_2)_i\neq r_i] + = \hat{n} d(c_1, r) + \hat{n}d(c_2, r) +\end{displaymath} +where the second equality follows from the fact that $r_i$ is either equal to +$(c_1)_i$ or $(c_2)_i$ when $(c_1)_i\neq (c_2)_i$. The other equalities simply +use the definition of the relative distance. + +I claim that one of the two secrets $s\in\{s_1, s_2\}$ is such that the +relative distance $d(\Enc(s), r)\leq \frac{1}{4} + \eps$. Otherwise, using the +identity proven above: +\begin{displaymath} + d(c_1, c_2) = d(c_1, r) + d(c_2, r)> \frac{1}{2} + 2\eps +\end{displaymath} +This implies that $\Enc(s_1)$ and $\Enc(s_2)$ agree on less than a $\frac{1}{2} +- 2\eps$ fraction of positions and contradicts the assumption on $\Enc$. + +Since one of the two secrets $s\in\{s_1,s_2\}$ is such that +$d(\Enc(s),r)\leq\frac{1}{4}+\eps$, by list-decoding the received answer $r$ at +distance $\frac{1}{4}+\eps$, we are guaranteed that the list $L$ of length $l$ +returned by the decoder contains one of the two secrets. By assumption, the +decoding takes polynomial time. + +\paragraph{2.} + \end{document} |