text:
\section{Introduction}

List decoding is a relaxation of the traditional unique decoding paradigm,
where one is allowed to output a list of codewords that are close to the
received word. This relaxation allows for designing list decoding algorithms
that can recover from scenarios where almost all of the redundancy could have
been corrupted~\cite{sudan,GS98,PV-focs05,GR-capacity}. In particular, one can
design binary codes from which one can recover from a $1/2-\varepsilon$ fraction of errors.
This fact has lead to many surprising applications in complexity theory-- see
e.g. the survey by Sudan~\cite{sudan-sigact} and Guruswami's thesis~\cite[Chap. 12]{G-thesis}.

The results mentioned above mostly deal with worst-case errors, where
the channel is considered to be an adversary that can corrupt any arbitrary
fraction of symbols (with an upper bound on the maximum fraction of such errors).
In this work, we deal with random and erasure noise models,
 which are weaker than the worst-case
errors model, and which also have interesting applications in complexity theory.

\subsection{Random Errors}
It is well-known that for worst-case errors, one
cannot uniquely recover the transmitted codeword if the total number of errors
exceeds half the distance. (We refer the reader to Section~\ref{sec:prelims}  for definitions
related to codes.)
List decoding circumvents this by allowing the decoder to output
multiple nearby codewords. In situations where the decoder has access to some
side information, one can prune the output list to obtain the transmitted
codeword. In fact, most of the applications of list decoding in complexity
theory crucially use side information. However, a natural question to ask
is what one can do in situations where there is no side information (this is
not an uncommon assumption in the traditional point-to-point communication
model).

In such a scenario, it makes sense to look at a weaker random noise model and try
to argue that the pathological cases that prevent us from decoding a code
with relative distance $\delta$ from more than $\delta/2$ fraction of errors
are rarely encountered.

Before we move on, we digress a bit to establish our notion of random errors.
In our somewhat non-standard model, we assume that the adversary can pick the
location of the $\rho$ fraction of error \textit{positions} but that the
errors themselves are random.
For the binary case, this model coincides with worst-case errors, so in
this work, we consider alphabet size $q\ge 3$. We believe that this is a nice
intermediary to the worst-case noise model and the more popular models of random
noise, where errors are \textit{independent} across different symbols. Indeed,
a result with high probability in our random noise model (for roughly
$\rho$ errors)
immediately implies a similar result for a more benign random noise model such as
the $q$-ary symmetric noise channel with cross-over probability $\rho$.\footnote{In
this model, every transmitted symbol   remains untouched with probability $1-\rho$
and is mapped to the other $q-1$ possible symbols with probability $\rho/(q-1)$. Finally, the noise acts independently on each symbol.} For the rest of the
paper, when we say random errors, we will be referring to the stronger random
noise model above.

\paragraph{Related Work.} The intuition that pathological worst-case errors are rare has been
formalized for certain families of codes. For example, McEliece showed that
for Reed-Solomon codes with distance $\delta$, with high probability, for a
fraction $\rho\le \delta-\varepsilon$ of random errors, the output list size is one~\cite{mceliece}.\footnote{The
actual result is slightly weaker: see Section~\ref{sec:randerrors} for more details.}
Further, for \textit{most} codes of rate $1-H_q(\rho)-\varepsilon$, with high
probability, for a $\rho$ fraction of random errors, the output list size is one. (This follows from
Shannon's famous result on the capacity of the $q$-ary symmetric channel:
for a proof, see e.g.~\cite{R-cocoon}.) It is also known that most
codes of rate $1-H_q(\rho)-\varepsilon$ have relative distance at least $\rho$.
Further, for $q\ge 2^{\Omega(1/\varepsilon)}$, it is known that such a code cannot
have distance more than $\rho+\varepsilon$:
this follows from the Singleton bound and the fact that for such an alphabet size,
$1-H_q(\rho) \ge 1-\rho-\varepsilon$ (cf.~\cite[Sec 2.2.2]{atri-thesis}).

\paragraph{Our Results.}
In our first main result, we show that the phenomenon above is universal, that is,
for \textit{every} $q$-ary code, with $q\ge 2^{\Omega(1/\varepsilon)}$, the following property
holds: if the code has relative distance $\delta$, then for any $\rho\le \delta -\varepsilon$
fraction of random errors, with high probability, the Hamming ball of fractional
radius $\rho$ around the
received word will only have the transmitted codeword in it. We would like to point out three
related points. First, our result implies that if we relax the worst-case error model to a
random error model, then combinatorially one can always correct \textit{twice} the
number of errors. Second, one cannot hope to correct more than a $\delta$ fraction of random
errors: it is easy to see that, for instance, for Reed-Solomon codes, \textit{any} error pattern of
relative Hamming weight $\rho>\delta$ will give rise to a list size greater than one. Finally, the
proof of our result follows from a fairly straightforward counting argument.

A natural follow-up question to our result is whether the lower bound of $2^{\Omega(1/\varepsilon)}$
on $q$ can be relaxed. We show that if $q$ is $2^{o(1/\varepsilon)}$, then the result above is \textit{not
true}.
This negative result follows from the following two observations/results. First, it is known that for
\textit{any} code with rate $1-H_q(\rho)+\varepsilon$, the average list size, over all possible received
words, is exponential. Second, it is known that Algebraic-Geometric (AG) codes over alphabets
of size at least $49$ can have relative distance \textit{strictly} bigger than $1-H_q(\rho)$ (cf.~\cite{handbook}).
However, these two results do not immediately imply the negative result for the random error case. In
particular, what we need to show is that there is at least one codeword $\myvec{c}$ such that for
most error patterns $\myvec{e}$ of relative Hamming weight $\rho$, the received word $\myvec{c}+\myvec{e}$ has at least one
codeword other than $\myvec{c}$ within a relative Hamming distance of $\rho$ from it. To show that this can indeed be
true for AG codes, we use a generalization of an ``Inverse Markov argument" from
Dumer et al.~\cite{DMS}.

\paragraph{A Cryptographic Application.}
In addition to being a natural noise model to study, list decoding in the random error model
has applications in cryptography. In particular, Kiayias and Yung have proposed cryptosystems
based on the hardness of decoding Reed-Solomon codes~\cite{rs-crypto}.
However, if for Reed-Solomon codes (of rate $R$), one can list decode $\rho$ fraction of
\textit{random} errors then the cryptosystem from~\cite{rs-crypto} can be broken for the
corresponding parameter settings. Since Guruswami-Sudan can solve this problem for $\rho\le 1-\sqrt{R}$
for \textit{worst-case} errors~\cite{GS98}, Kiayias and Yung set the parameter $\rho>1-\sqrt{R}$. Beyond the
$1-\sqrt{R}$ bound, to the best of our knowledge,
the only known algorithms to decode Reed-Solomon codes are the following trivial ones:
(i) Go through all possible $q^k$ codewords and output all the codewords with Hamming distance
of $\rho$ from the received word; and (ii) Go through all possible $\binom{n}{\rho n}$ error locations
and output the codeword, if any, that agrees in the $(1-\rho)n$ ``non-error" locations.

It is interesting to note that each of the three algorithms mentioned above work in the
stronger model of worst-case errors. However, since we only care about decoding from random errors, one
might hope to design better algorithms that make use of the fact that the errors are random.
In this paper, we show that (essentially) the proof of our first main result
implies a related result that in turn implies a modest improvement in the running time of algorithms
to decode Reed-Solomon codes from $\rho>1-\sqrt{R}$ fraction of random errors. The related result
states the following: for \text{any} code with relative distance $\delta$ (over a large enough
alphabet) with high probability, for a $\rho$ fraction of random errors, Hamming balls of
fractional radius $\delta-\varepsilon$ around the received word only have the transmitted codeword in them.\footnote{A similar result was shown for Reed-Solomon codes by McEliece~\cite{mceliece}.} Note that
unlike the statement of our result mentioned earlier, we are considering Hamming balls of radius
\textit{larger} than the fraction of errors. This allows us to improve the second trivial
algorithm in the paragraph above so that one needs to verify fewer ``error patterns."
This leads to an asymptotic improvement in the running time over both of the trivial
algorithms for certain setting of parameters, though the running time is still exponential
and thus, too expensive to
break the Kiayias-Yung cryptosystem.

\subsection{Erasures}

In the second part of the paper, we consider the erasure noise model, where the decoder knows the
locations of the errors. (However, the error locations are still chosen by
 the adversary.) Intuitively, this noise model
is weaker than the general worst-case noise model as the decoder knows for sure which locations are
uncorrupted. This intuition can also be formalized. E.g., it is known that for a $\rho$ fraction of
worst-case errors, the list decoding capacity is $1-H_q(\rho)$, whereas for a $\rho$ fraction of
 erasures, the list decoding capacity is $1-\rho$ (cf. \cite[Chapter 10]{G-thesis}).
Note that the capacity for erasures is \textit{independent} of the alphabet size.
As another example, for a linear code, a combinatorial guarantee on list decodability from
erasures gives a polynomial time list decoding algorithm. By contrast, such a result is
not known for worst-case errors.

As is often the case, the capacity result is proven by random coding arguments.
A natural quest then is to design explicit linear codes that achieve the list decoding capacity for erasures, and is an important milestone in the program of designing explicit codes that achieve list decoding capacity for worst-case
errors. This goal is the primary motivation for our second main result.

\paragraph{Our Result and Related Work.} For large enough alphabets, explicit linear codes that achieve list
decoding capacity for erasures are not hard to find: e.g., Reed-Solomon codes achieve the capacity. For
smaller alphabets, the situation is much different. For binary codes, Guruswami
presented explicit linear codes that can handle $\rho=1-\varepsilon$ fraction of erasures with rate
$\Omega\left(\frac{\varepsilon^2}{\log(1/\varepsilon)}\right)$~\cite{Gur-erasures}. For alphabets of size $2^t$, $1-\varepsilon$ fraction
of erasures can be list decoded with explicit linear codes of rate
 $\Omega\left(\frac{\varepsilon^{1+1/t}}{t^2\log(1/\varepsilon)}\right)$~\cite[Chapter 10]{G-thesis}. Thus,
especially for binary codes, an explicit code with capacity of $1-\rho$ is still a lofty goal.
(In fact, breaking the $\varepsilon^2$ rate barrier for \textit{polynomially} small $\varepsilon$ would
imply explicit construction of certain bipartite Ramsey graphs, solving an open
question~\cite{Gur-erasures}.)

To gain a better understanding about codes that achieve list decoding capacity for erasures, a natural
question is to ask whether \textit{concatenated codes} can achieve the list decoding capacity for erasures.
Concatenated codes are the preeminent method to construct good list decodable codes over
small alphabets. In fact, the best explicit list decodable binary codes (for both erasures~\cite{Gur-erasures} and
worst-case errors~\cite{GR-multilevel}) are concatenated codes. Briefly, in code concatenation, an ``outer" code over a
large alphabet is first used to encode the message. Then ``inner" codes over the smaller alphabet
are used to encode each of the symbols in the outer codeword.  These inner codes typically have a
much smaller block length than the outer code, which allows one to use brute-force type algorithms
to search for ``good" inner codes. Also note that the rate of the concatenated code is the
product of the rate of the outer and inner codes.

Given that concatenated codes have such a rigid structure, it seems plausible that such codes would
not be able to achieve list decoding capacity. For the worst-case error model, Guruswami and Rudra showed that there
do exist concatenated codes that achieve list decoding capacity~\cite{atri-venkat-soda-08}.
However, for erasures there is an additional potential complication that does not arise for the
worst-case error case. In particular, consider erasure patterns in which $\rho$ fraction of the outer symbols are
completely erased. It is clear by this example that the outer code needs to have rate very close to $1-\rho$. However,
note that to approach list decoding capacity for erasures, the concatenated code needs to have
rate $1-\rho-\varepsilon$. This means that the inner codes need to have rate very close to $1$.
By contrast, even though the result of~\cite{atri-venkat-soda-08} has some restrictions on the rate
of the inner codes, it is not nearly as stringent as the requirement above.
(The restriction in~\cite{atri-venkat-soda-08} seems to be an artifact of the proof, whereas
for erasures, the restriction is unavoidable.)
Further, this restriction
on the inner rate is just by looking at a specific class of erasure patterns. It is reasonable to
wonder if when taking into account all possible erasure patterns, we can rule out the possibility
of concatenated codes achieving the list decoding capacity for erasures.

In our second main result, we show that concatenated codes \textit{can} achieve the list decoding
capacity for erasures. In fact, we show that choosing the outer code to be a Folded Reed-Solomon
code (\cite{GR-capacity}) and picking the inner codes to be random independent linear codes with rate $1$, will with high
probability, result in a linear code that achieves the list decoding capacity for erasures. We
show a similar result (but with better bounds on the list size) when the outer code is also chosen
to be a random linear code. Both of these ensembles were shown to achieve the list decoding
capacity for errors in~\cite{atri-venkat-soda-08}, although, as mentioned earlier, the result for errors
holds for a superset of concatenated codes (as the inner codes could have rates strictly less
than $1$). The proof of our result is similar to the proof structure in~\cite{atri-venkat-soda-08}.
Because we are dealing with the more benign erasure noise model, some of the calculations in
our proofs are much simpler than the corresponding ones in~\cite{atri-venkat-soda-08}.

\paragraph{Approximating NP Witnesses.} We conclude this section by pointing out that an application of
binary codes that are list decodable from erasures is to the problem of approximating NP-witnesses~\cite{GHLP,KS}.
For any NP-language $L$, we have a polynomial-time decidable relation $R_L(\cdot,\cdot)$ such that
$x\in L$ if and only if there exists a polynomially sized witness $w$ such that $R_L(x,w)$ accepts.
Thus, for an NP-complete language we do not expect to be able to compute the witness $w$ in
polynomial time
given $x$. A natural notion of approximation is the following: given an $\varepsilon$ fraction of the bits
in a
a correct witness $w$, can we verify if $x\in L$ in polynomial time? The results in
\cite{GHLP,KS} show that such an approximation is not possible unless P$=$NP.

To be more precise, G\'{a}l et al. (\cite{GHLP}) consider the following problem: given a SAT formula $\phi$ over
$n$ variables can we, in polynomial time, compute another SAT formula $\phi'$ over
$N=\mathrm{poly}(n)$ variables such that given $\varepsilon N$ bits from a satisfying assignment to
$\phi'$, we can compute a satisfying assignment to the original formula $\phi$?

Kumar and Sivakumar's (\cite{KS}) reduction works for any NP-language
$L$. However, their reduction computes a polynomial-time computable relation $R'_L$ (with
witness size $N=\mathrm{poly}(n)$),
which is different from the original  predicate $R_L$ such that the knowledge of
$\varepsilon N$ many bits of some satisfying witness for $R'_L$ can be used in polynomial time to compute
a satisfying witness for $R'_L$. Both of these results are proven by picking a
linear binary code $C$ that can be list decoded from a $1-\varepsilon$ fraction of erasures and ``encoding"
$C(x)$ (where $x$ is the input) into the definition of $\phi'$ (in the case of~\cite{GHLP})
 or $R'_L$ (in the case of~\cite{KS}). The intuition behind these reductions
is that given sufficiently many bits
of a satisfying witness, we can obtain a list of potentially satisfying witnesses by running the list
decoding algorithm for $C$ to recover from the erasures. (The connection to list decoding was
implicit in~\cite{GHLP}-- it was made explicit in~\cite{KS}.)

Guruswami and Sudan (\cite{GS2000}) show that the reductions above can be made to work with $\varepsilon=N^{-1/2+\gamma}$ for
the Kumar and Sivakumar problem and with $\varepsilon=N^{-1/4+\gamma}$ for the G\'{a}l et al. problem (for any
constant $\gamma>0$). An explicit linear code that meets the list decoding capacity for erasures will
improve the value of $\varepsilon$ above to $N^{-1+\gamma}$ and $N^{-1/2+\gamma}$, respectively.

\paragraph{Organization of the Paper.} We begin with some preliminaries in Section~\ref{sec:prelims}.
We present our first main result on random codes in Section~\ref{sec:randerrors} and our
second main result on erasures in Section~\ref{sec:concatcodes}.

\section{Preliminaries}
\label{sec:prelims}
For an integer $m\ge 1$, we will use $[m]$ to denote the set $\{1,\dots,m\}$.

\paragraph{Basic Coding Definitions.}
A code $C$ of {\em dimension} $k$ and {\em block length} $n$ over an
alphabet $\Sigma$ is a subset of $\Sigma^n$ of size $|\Sigma|^k$. The
{\em rate} of such a code equals $k/n$.  Each $n$-tuple in $C$ is called a
codeword.
Let $\mathbb{F}_q$ denote the field with $q$
elements. A code $C$ over
$\mathbb{F}_q$ is called a linear code if $C$ is a subspace of $\mathbb{F}_q^n$. In
this case the dimension of the code coincides with the dimension of
$C$ as a vector space over $\mathbb{F}_q$. By abuse of notation we can also
think of a linear code $C$ as a map from an element in $\mathbb{F}_q^k$ to its
corresponding codeword in $\mathbb{F}_q^n$, mapping a row vector $\myvec{x} \in \mathbb{F}_q^k$ to a vector
$\myvec{x} \myvec{G} \in \mathbb{F}_q^n$ via a $k\times n$ matrix $\myvec{G}$ over $\mathbb{F}_q$ which
is referred to as the generator matrix.

The Hamming distance between two vectors in $\myvec{x},\myvec{y}\in\Sigma^n$, denoted by $\Delta(\myvec{x},\myvec{y})$,
 is the number
of places they differ in. The (minimum) distance of a code $C$ is the
minimum Hamming distance between any two distinct codewords
from $C$. The relative distance is the ratio of the distance to the
block length.

We will need the following notions of the weight of a vector.  Given a
vector $\myvec{v}\in\{0,1,\dots,q-1\}^{n}$, its Hamming weight, which is the
number of non-zero entries in the vector, is denoted by
$\textsc{wt}(\myvec{v})$.  Given a vector $\myvec{y}=(y_1,\dots,y_n)\in
\{0,\dots,q-1\}^n$ and a subset $S\subseteq [n]$, $\myvec{y}_S$ will denote
the subvector $(y_i)_{i\in S}$, and
$\textsc{wt}_S(\myvec{y})$ will denote the Hamming weight of $\myvec{y}_S$.

\paragraph{Code Concatenation.}
Concatenated codes are constructed from two different types of codes
that are defined over alphabets of different sizes.  If we are
interested in a concatenated code over $\mathbb{F}_q$,
then the \textit{outer code}
$C_{\rm out}$ is defined over $\mathbb{F}_Q$, where $Q=q^k$ for some positive
integer $k$, and has block length $N$. The second type of codes, called
the \textit{inner codes}, and which are denoted by $C_{\rm in}^1,\dots,C_{\rm in}^N$,
are defined over $\mathbb{F}_q$ and are each of dimension $k$ (note that the
message space of $C_{\rm in}^i$ for all $i$ and the alphabet of $C_{\rm out}$ have
the same size).  The concatenated code, denoted by
$C=C_{\rm out}\circ(C_{\rm in}^1,\dots,C_{\rm in}^N)$, is defined as follows: Let the
rate of $C_{\rm out}$ be $R$ and let the block lengths of
$C_{\rm in}^i$ be $n$ (for $1\le i\le N$). Define
$K=RN$ and $r=k/n$. The input to $C$ is a vector
$\myvec{m}=\angles{m_1,\dots,m_K}\in (\mathbb{F}_q^k)^K$. Let
$C_{\rm out}(\myvec{m})=\angles{x_1,\dots,x_N}$.  The codeword in $C$
corresponding to $\myvec{m}$ is defined as follows
\[C(\myvec{m})=\angles{C_{\rm in}^1(x_1),C_{\rm in}^2(x_2),\dots,C_{\rm in}^N(x_N)}.\]

The outer code $C_{\rm out}$ in this paper will either be a random linear code over $\mathbb{F}_Q$
or the folded Reed-Solomon code from~\cite{GR-capacity}.  In the case
when $C_{\rm out}$ is random linear, we will pick $C_{\rm out}$ by selecting $K=RN$
vectors uniformly at random from $\mathbb{F}_Q^N$ to form the rows of the
generator matrix. For every position $1\le i\le N$, we will choose an
inner code $C_{\rm in}^i$ to be a random linear code over $\mathbb{F}_q$ of block
length $n$ and rate $r=k/n$. In particular, we will work with the
corresponding generator matrices $\myvec{G}_i$, where every
$\myvec{G}_i$ is a random $k\times n$ matrix over $\mathbb{F}_q$. All the
generator matrices $\myvec{G}_i$ (as well as the generator matrix for
$C_{\rm out}$, when we choose a random $C_{\rm out}$) are chosen independently.
This fact will be used crucially in our proofs.

\paragraph{List Decoding.} We define some terms related to list decoding.
\begin{definition}[List decodable code for errors]
For $0 < \rho <1$ and an integer $L \ge 1$, a code $C \subseteq
\Sigma^n$ is said to be $(\rho,L)$-list decodable if for every
$\myvec{y}\in\Sigma^n$, the number of codewords in $C$ that are within Hamming
distance $\rho n$ from $y$ is at most $L$.
\end{definition}

Given a vector $\myvec{c}=(c_1,\dots,c_n)\in\Sigma^n$ and an erased received word $\myvec{y}=(y_1,\dots,y_n)\in(\Sigma\cup\{?\})^n$,\footnote{$?$ denotes an erasure.} we will use
$\myvec{c}\simeq \myvec{y}$ to denote the fact that for every $i\in [n]$ such that $y_i\neq ?$, $c_i=y_i$. With this
definition, we are ready to define the notion of list decodability for erasures. Further, for an erased received
word, we will use $\textsc{wt}(\myvec{y})$ to denote the number of erased positions.

\begin{definition}[List decodable code for erasures]
For $0 < \rho <1$ and an integer $L \ge 1$, a code $C \subseteq
\Sigma^n$ is said to be $(\rho,L)_{led}$-list decodable if for every
$\myvec{y}\in(\Sigma\cup\{?\})^n$ with $\textsc{wt}(\myvec{y})\le \rho n$, the number of codewords $\myvec{c}\in C$
such that $\myvec{c}\simeq \myvec{y}$ is at most $L$.
\end{definition}

\paragraph{Reed-Solomon and Related Codes.}
The classical family of Reed-Solomon (RS) codes over a field $\mathbb{F}$ are
defined to be the evaluations of low-degree polynomials at a sequence
of distinct points of $\mathbb{F}$. Folded Reed-Solomon codes are obtained by
viewing the RS code as a code over a larger alphabet $\mathbb{F}^s$ by
bundling together $s$ consecutive symbols for some folding parameter
$s$.
We will not need any specifics of folded RS codes (in fact, even their
definition) beyond certain properties that we recall in Section~\ref{sec:concatcodes}.

\section{Random Errors}
\label{sec:randerrors}

In this section we consider the random noise model mentioned in the introduction:
the error locations are adversarial but the errors themselves are random.
Our main result is the following.

\begin{theorem}
\label{thm:dist-list-one}
Let $0<\varepsilon,\delta<1$ be reals and let $q$ and $n\ge \Omega(1/\varepsilon)$ be positive integers.
Let $\Sigma=\{0,1,\dots,q-1\}$.\footnote{We will assume that $\Sigma$ is equipped with a
monoid structure,
i.e. for any $a,b\in\Sigma$, $a+b\in \Sigma$ and $0$ is the identity element.} Let $0<\rho\le\delta-\varepsilon$ be a real.
Let $C$ be a code over $\Sigma$ of block length $n$ and
relative distance $\delta$.
Let
$S\subseteq [n]$ with $|S|= (1-\rho)n$. Then the following hold:
\begin{itemize}
\item[(a)]
If $q\ge 2^{\Omega(1/\varepsilon)}$, then
for every codeword $\myvec{c}$ and all but a $q^{-\Omega(\varepsilon n)}$ fraction of
error patterns $\myvec{e}\in \Sigma^n$ with $\textsc{wt}(\myvec{e})=\rho n$ and $\textsc{wt}_S(\myvec{e})=0$, the
only codeword within the Hamming ball of radius $\rho n$ around the
received word $\myvec{c}+\myvec{e}$ is $\myvec{c}$.
\item[(b)] Let $\gamma>0$.
If $q> \max\left(n,\left(\frac{e}{1-\delta+\varepsilon}\right)^{\left\lceil \frac{1}{\gamma}\right\rceil}\right)$, then
for every codeword $\myvec{c}$ and all but a $(q-1)^{-((1-\gamma)\varepsilon/2-(1-\delta)\gamma)n}$ fraction of
error patterns $\myvec{e}\in \Sigma^n$ with $\textsc{wt}(\myvec{e})=\rho n$ and $\textsc{wt}_S(\myvec{e})=0$, the
only codeword within the Hamming ball of radius $(\delta-\varepsilon) n$ around the
received word $\myvec{c}+\myvec{e}$ is $\myvec{c}$.
\end{itemize}
\end{theorem}

\iffalse
As a Reed-Solomon code of rate $R$ has relative distance at least $1-R$,
part (a) of
Theorem~\ref{thm:dist-list-one} implies Theorem~\ref{thm:RS-list-one}.\footnote{
Theorem~\ref{thm:RS-list-one} also includes error patterns with sub-linear
Hamming weight while Theorem~\ref{thm:dist-list-one} only considers error
patterns of linear Hamming weight. However, this is not an issue since
the number of error patterns with sub-linear Hamming
weight is an exponentially small
fraction of error patterns with linear Hamming weight.}
Further, Theorem~\ref{thm:dist-list-one} states that one can deal with strictly
less than a $\delta$ fraction of errors even if the error locations are
\textit{arbitrary} and the errors themselves are random.
\fi

A weaker version of Theorem~\ref{thm:dist-list-one} was previously known for RS codes~\cite{mceliece}.
(Though the bounds for part (b) are better in~\cite{mceliece}.) In particular, McEliece showed Theorem~\ref{thm:dist-list-one}
for RS codes but over \textit{all} error patterns of Hamming weight $\rho n$. In other words, Theorem~\ref{thm:dist-list-one}
implies the result in~\cite{mceliece} if we average our result over all subsets $S\subseteq [n]$ with
$|S|=\rho n$.

Part (a) of Theorem~\ref{thm:dist-list-one} implies that for $e\le (\delta-\varepsilon)n$ random errors,
with high probability, the Hamming ball of radius $e$ has one codeword in it. Note that this
is \textit{twice} the number of errors for which an analogous result can be shown
for worst-case errors.
Part (b) of Theorem~\ref{thm:dist-list-one} implies the following property
of Reed-Solomon codes (where we pick $\varepsilon=4R$ and $\gamma=1/2$).

\begin{corollary}
\label{cor:rs-avg-list-one}
Let $k\le n< q$ be integers such that $q>\left(\frac{n}{k}\right)^2$. Then
the following property holds for Reed-Solomon codes of dimension $k$ and
block length $n$ over $\mathbb{F}_q$. For at least $1-q^{-\Omega(k)}$ fraction of
error patterns $\myvec{e}$ of Hamming weight {\em at most} $n-4k$ and any codeword
$\myvec{c}$, the only codeword that agrees in at least $4k$ positions with
$\myvec{c}+\myvec{e}$ is $\myvec{c}$.
\end{corollary}

We would like to point out that in Corollary~\ref{cor:rs-avg-list-one}, the radius of the Hamming
ball can be \textit{larger} than the number of errors. This can be used to slightly improve
upon the best known algorithms to decode RS codes from random errors beyond the Johnson
bound for super-polynomially large $q$. See Section~\ref{sec:random-algo} for
more details.

A natural question is whether the lower bound of $q\ge 2^{\Omega(1/\varepsilon)}$ in part (a) of Theorem
\ref{thm:dist-list-one} can be improved. In Section~\ref{sec:alphabet-lb} we show that this is
not possible.

\paragraph{Proof of Theorem~\ref{thm:dist-list-one}.}
Let $\myvec{c}\in C$ be the transmitted codeword. For an $\a\ge 1-\delta+\varepsilon$,
we call an error pattern
$\myvec{e}$ (with $\textsc{wt}(\myvec{e})=\rho n$ and $\textsc{wt}_S(\myvec{e})=0$) $\a$-\textit{bad} if there exits
a codeword
$\myvec{c}'\neq\myvec{c}\in C$ such that $\Delta(\myvec{c}+\myvec{e},\myvec{c}')= (1-\a)n$ (and every
other codeword has a larger Hamming distance from $\myvec{c}+\myvec{e}$). We will
show that the number of $\a$-bad error patterns (over all
$\a\ge 1-\delta+\varepsilon$) is an exponentially
small fraction of error patterns $\myvec{e}$ with $\textsc{wt}(\myvec{e})=\rho n$ and $\textsc{wt}_S(\myvec{e})=0$,
which will prove the theorem.

Fix $\a\ge 1-\delta+\varepsilon$. Associate every $\a$-bad error pattern $\myvec{e}$ with the
lexicographically first codeword $\myvec{c}'\neq\myvec{c}\in C$ such that $\Delta(\myvec{c}+\myvec{e},\myvec{c}')=(1-\a)n$.
Let $A\subseteq [n]$ be the set of positions where
$\myvec{c}'$ and $\myvec{c}+\myvec{e}$ agree. Further, define $S_0=S\cap A$, $S_1=A\cap ([n]\setminus S)$
and $\b=|S_0|/n$.
Thus, for every $\a$-bad error pattern $\myvec{e}$, we can associate such a pair of
subsets $(S_0,S_1)\subseteq S\times ([n]\setminus S)$. Hence, to count the number of $\a$-bad
error patterns it suffices to count for each possible pair $(S_0,S_1)$,
with $|S_0|=\b n$ and $|S_1|=(\a -\b)n$ for some $\a-\rho\le \b\le \a$, the
number of $\a$-bad patterns that can be associated with it. (The lower and upper bounds on
$\b$ follow from the fact that $S_1\subseteq [n]\setminus S$ and $S_0\subseteq A$,
respectively.)

Fix sets $S_0\subseteq S$ and $S_1\subseteq [n]\setminus S$
with $|S_0|=\b n$ and $|S_1|=(\a-\b)n$ for some $\a-\rho\le \b\le \a$.
To upper bound the number of $\a$-bad
error patterns that are associated with $(S_0,S_1)$, first note that such
error patterns take all the $(q-1)^{(\rho-\a+\b)n}$ possible
values at the positions in $[n]\setminus(S\cup S_1)$. Fix a vector
$\myvec{x}$ of length $n-|S|-|S_1|$ and consider all the $\alpha$-bad
error patterns $\myvec{e}$
such that $\myvec{e}_{[n]\setminus (S\cup S_1)}=\myvec{x}$.
Recall that each error pattern is associated with a codeword $\myvec{c}'\neq \myvec{c}$
such that $\myvec{c}'$ and $\myvec{c}+\myvec{e}$ agree exactly in the positions $S_0\cup S_1$.
Further, such a codeword $\myvec{c}'$ is associated with exactly one $\a$-bad
error pattern $\myvec{e}$, where $\myvec{e}_{[n]\setminus (S\cup S_1)}=\myvec{x}$. (This is
because fixing $\myvec{c}'$ fixes $\myvec{e}_{S_1}$ and $\myvec{e}_S$ is already fixed by
the definition of $S$.) Thus, to upper bound the number of $\a$-bad
error patterns associated with $(S_0,S_1)$, where $\myvec{e}_{[n]\setminus (S\cup S_1)}=\myvec{x}$ (call this number $N_{\a,S_0,S_1,\myvec{x}}$),
we will upper bound the number of such codewords $\myvec{c}'$. Note that as $C$ has
relative distance $\delta n$, once any  $(1-\delta)n+1$ positions are fixed,
there is at most one codeword that agrees with the fixed positions (if there
is no such codeword then the corresponding ``error pattern" does not exist).
Thus, there is at most one possible
$\myvec{c}'$  once we fix (say) the ``first" $(1-\delta)n+1-|S_0|$
values of $\myvec{e}_{S_1}$ (recall that $\myvec{c}'_{S_0}=\myvec{c}_{S_0})$. This implies that
\[N_{\a,S_0,S_1,\myvec{x}}\le (q-1)^{(1-\delta-\b)n+1}.\]
Let $M_{\a}$ be the  number of choices for $(S_0,S_1)$, which is just the number of
choices for $A$. As
the number of choices for $\myvec{x}$ is $(q-1)^{(\rho-\a+\b)n}$,  the
number of $\a$-bad error patterns is at most
\begin{equation}
\label{eq:num-bad-pattern}
M_{\a}\cdot (q-1)^{(\rho-\a+\b)n}\cdot (q-1)^{(1-\delta-\b)n+1}=M_{\a}\cdot(q-1)^{(1-\delta-\a)n+1}\cdot (q-1)^{\rho n}.
\end{equation}

\paragraph{Proof of part(a).} Note that the number of $\a$-bad patterns for
any $\a\ge 1-\delta+\varepsilon$ is upper bounded by
\[M_{\a}\cdot(q-1)^{-\varepsilon n+1}\cdot (q-1)^{\rho n}.\]
We trivially upper bound $M_{\a}$ by $2^n$.
Recalling that there are $(q-1)^{\rho n}$ error patterns $\myvec{e}$ with $\textsc{wt}(\myvec{e})=\rho n$
and $\textsc{wt}_S(\myvec{e})=0$ and that $\a$ can take at most $n$ values, the fraction
of $\a$-bad patterns (over all $\a\ge 1-\rho\ge 1-\delta+\varepsilon$) is at most
\[n2^{n}(q-1)^{-\varepsilon n+1}\le (q-1)^{\left(-\varepsilon +\frac{2}{\log(q-1)}+\frac{1}{n}\right)n}\le (q-1)^{-\varepsilon n/3}\le q^{-\varepsilon n/6},\]
where the first inequality follows from the fact that $n\le 2^n$, the
second inequality is true for $n\ge 3/\varepsilon$ and $q\ge 2^{6/\varepsilon}$ and the last
inequality follows from the inequality
$(q-1)\ge \sqrt{q}$ (which in turn is true for $q\ge 3$).

\paragraph{Proof of part (b).} Note that $M_{\a}=\binom{n}{\a n}\le (e/\a)^{\a n}$. Thus, the number of $\a$-bad error patterns is upper bounded by
\[ (q-1)^{\left(1-\delta-\a+\a\cdot\frac{\log(e/\a)}{\log(q-1)}\right)n+1}\cdot (q-1)^{\rho n}
\le (q-1)^{(1-\delta-\a(1-\gamma))n+1}\cdot (q-1)^{\rho n}\le
(q-1)^{(-(1-\gamma)\varepsilon+\gamma(1-\delta))n+1}\cdot (q-1)^{\rho n},
\]
where the inequalities follow from the facts that $q> \left(\frac{e}{1-\delta+\varepsilon}\right)^{1/\gamma}$ and $\a\ge 1-\delta+\varepsilon$.
Recalling that there are $(q-1)^{\rho n}$ error patterns $\myvec{e}$ with $\textsc{wt}(\myvec{e})=\rho n$
and $\textsc{wt}_S(\myvec{e})=0$ and that $\a$ can take at most $n$ values, the fraction
of $\a$-bad patterns (over all $\a\ge 1-\delta+\varepsilon$) is at most
\[n(q-1)^{(-(1-\gamma)\varepsilon+(1-\delta)\gamma)n+1}\le (q-1)^{\left(-(1-\gamma)\varepsilon+\gamma(1-\delta)+\frac{2}{n}\right)n}\le
(q-1)^{\left(-\frac{(1-\gamma)\varepsilon}{2}+\gamma(1-\delta)\right)n},\]
where the first inequality follows from the fact that $q>n$ and the
second inequality is true for $n\ge 4/((1-\gamma)\varepsilon)$.
\hfill\blackslug

\subsection{An Implication of Corollary~\ref{cor:rs-avg-list-one}}
\label{sec:random-algo}

To the best of our knowledge,
for $e>n-\sqrt{kn}$, the only known algorithms to decode Reed-Solomon (RS) codes
from $e$ random errors are the trivial ones:
(i) Go through all possible codewords and output the closest codeword--
this takes $2^{O(k\log{q})}\cdot n$ time and (ii) Go through all
possible $\binom{n}{e}$ error locations and check that the received word
outside the purported error locations is indeed a RS codeword-- this
takes $2^{O((n-e)\log(n/(n-e)))}\cdot O(n^2)$ time.

If $e\le n-4k$, then by Corollary~\ref{cor:rs-avg-list-one}, we can go through all
the $\binom{n}{4k}$ choices of subsets of size $4k$ and check if the received word
projected down to the subset lies in the corresponding projected down RS code.
This algorithm takes $2^{O(k\log(n/k))}\cdot O(n^2)$ time, which is better than the
trivial algorithm (ii) mentioned above for $e$ in $n-\omega(k)$.
Further, this algorithm is better than the trivial algorithm (i) when $q$ is
super-polynomially large in $n$.

\subsection{On the Alphabet Size in Theorem~\ref{thm:dist-list-one}}
\label{sec:alphabet-lb}

It is well-known that \textit{any} code that is $(\rho,L)$-list decodable that also has rate
at least $1-H_q(\rho)+\varepsilon$ needs to satisfy $L=q^{\Omega(\varepsilon n)}$ (cf.~\cite{G-thesis}).
A natural way to try to show that part (a) of Theorem~\ref{thm:dist-list-one} is false for
$q\le 2^{o(1/\varepsilon)}$ is to look at codes whose relative distance is strictly larger than
$1-H_q(\rho)$. Algebraic-geometric (AG) codes are a natural candidate since they can
beat the Gilbert-Varshamov bound for an alphabet size of at least $49$ (cf. \cite{handbook}). The only catch is that the lower bound on
$L$ follows from an average case argument and we need to show that over \textit{most} error patterns,
the list size is more than one. For this we need an ``Inverse Markov argument," like one in
~\cite{DMS}.

(The argument above was suggested to us by Venkat Guruswami.)

We begin with the more general statement of the ``Inverse Markov argument" from~\cite{DMS}. (We thank
Madhu Sudan for the statement and its proof.)

\begin{lemma}
\label{lem:inverse-markov}
Let $G=(L,R,E)$ be a bipartite graph with $|L|=n_L$ and $|R|=n_R$. Let the average left degree of $G$ be denoted by $\bar{d_L}$.
Note that the average right degree is $\bar{d_R}=\frac{n_L\cdot d_L}{n_R}$.
Then the following statements are true:
\begin{itemize}
\item[(i)] If we pick an edge $e=(u,v)$ uniformly at random from $E$, then the probability that\footnote{For any vertex $v$, we denote its degree by $d(v)$.}
$d(v)\le \varepsilon \bar{d_R}$ is at most $\varepsilon$.
\item[(ii)] If $G$ is $d$-left regular then consider the following process: Uniformly at random
pick a vertex $u\in L$. Then uniformly at random pick a vertex $v\in R$ in $u$'s neighborhood. Then the
probability that $d(v)\le \varepsilon \frac{ d n_L}{n_R}$ is at most $\varepsilon$.
\end{itemize}
\end{lemma}
\begin{proof}
We first note that (ii) follows from (i) as the random process in (ii) ends up picking edges uniformly
at random from $E$.

To conclude, we prove part (i). Consider the set $R'\subseteq R$ such that $v\in R'$ satisfies
$d(v)\le \varepsilon \bar{d_R}$. Note that that the maximum number of edges that have an end-point in
$R'$ is at most $\varepsilon \bar{d_R}\cdot n_R = \varepsilon |E|$. Thus, the probability that a uniformly random
edge in $E$ has an end point in $R'$ is upper bounded by $\varepsilon |E|/|E| =\varepsilon$, as desired.
\end{proof}

The following is an easy consequence
of Lemma~\ref{lem:inverse-markov} and the standard probabilistic method used to prove the lower bound
for list decoding capacity.

\begin{lemma}
\label{lem:av-bad-ball}
Let $q\ge 2$ and $0\le \rho < 1-1/q$. Then the following holds for large enough $n$.
Let $C\subseteq \{0,\dots,q-1\}^n$ be a code with rate $1-H_q(\rho)+\gamma$. Then there exists a codeword $\myvec{c}\in C$
such that for at least a $1-q^{-\Omega(\gamma n)}$ fraction of error patterns $\myvec{e}$ of Hamming weight at most
$\rho n$,
it is true that the Hamming ball of radius $\rho n$ around $\myvec{c} +\myvec{e}$ has at least two codewords from
$C$ in it.
\end{lemma}
\begin{proof}
Define the bipartite graph $G_{C,\rho}=(C,\{0,\dots,q-1\}^n,E)$
as follows. For every $\myvec{c}\in C$, add $(\myvec{c},\myvec{y})\in E$ such that $\Delta(\myvec{c},\myvec{y})\le \rho n$. Note that
$G_{C,\rho}$ is a $\vol{q}(\rho n)$-left regular bipartite graph, where
$\vol{q}(r)$ is the volume of the $q$-ary Hamming ball with radius $r$. Note that the graph has an
average right degree of
\[\bar{d_R}= \frac{\vol{q}(\rho n) \cdot q^{(1-H_q(\rho)+\gamma)n}}{q^n} \ge q^{\gamma n-o(n)},\]
where in the above we have used the following well known inequality (cf.~\cite{MS}):
\[\vol{q}(\rho n)\ge q^{H_q(\rho )n-o(n)}.\]
Thus, by part (b) of Lemma~\ref{lem:inverse-markov} (with $\varepsilon=(\bar{d}_R)^{-1}\le q^{-\gamma n+o(n)}$), we have
\[\mathop{\bf Pr}\limits_{\myvec{c}\in C}\mathop{\bf Pr}\limits_{\substack{\myvec{e}\in \{0,\dots,q-1\}^n\\\textsc{wt}(\myvec{e})\le \rho n}}\left[ \myvec{c}+\myvec{e}\text{ has at most one  codeword within Hamming distance } \rho n\right] \le q^{-\gamma n +o(n)}.\]
Thus, there must exist at least one codeword $\myvec{c}\in C$ with the required property.
\end{proof}

Thus, given Lemma~\ref{lem:av-bad-ball},  we can prove that part (a) of Theorem~\ref{thm:dist-list-one}
is not true for a certain value of $q$ if there exists a code $C\subseteq \{0,\dots,q-1\}^n$ with relative
distance $\delta$ such that it has rate at least $1-H_q(\delta -\varepsilon)+\gamma$ for some $\gamma >0$. Now it
is known that for fixed $\alpha >0$, $H_q(\alpha) \ge \alpha + \Omega\left(\frac{1}{\log{q}}\right)$
(cf.~\cite[Lecture 7]{sudan-notes}).
Thus, we would be done if we could find a code with relative distance $\delta$ and rate at least
\[1-\delta+\varepsilon +\gamma -O(1/\log{q}).\]
For $q\le 2^{o(1/\varepsilon)}$, the bound above for small enough $\varepsilon$ is upper bounded by
$1-\delta -\varepsilon-\frac{1}{\sqrt{q}-1}$
(assuming that $\gamma=\Theta(\varepsilon)$).
It is known that AG codes over alphabets of size $\ge 49$ with relative distance $\delta$ exist that achieve a rate of $1-\delta-\frac{1}{\sqrt{q}-1}$. Thus, for $49\le q\le 2^{o(1/\varepsilon)}$, AG codes over alphabets of size
$q$ are the required codes.

\section{Concatenated Codes}
\label{sec:concatcodes}

This section first shows that with folded Reed-Solomon codes and
independently chosen small random linear inner codes, the resulting
concatenated code can achieve erasure capacity in a list decoding setting.
A similar result holds when the outer code is a random linear code,
and this result is presented second.

\subsection{Folded Reed-Solomon Outer Code}
\begin{theorem}
\label{thm:frs-concat}
Let $q$ be a prime power and let $0<R \le 1$ be an arbitrary rational number.
Let $n,K,N\ge 1$ be large enough integers such that $K=RN$.
Let $C_{\rm out}$ be a folded Reed-Solomon code over $\mathbb{F}_{q^{n}}$ of block
length $N$ and rate $R$. Let $C_{\rm in}^1,\dots,C_{\rm in}^N$ be random linear
codes over $\mathbb{F}_q$, where $C_{\rm in}^i$ is generated by a random $n\times n$
matrix $\myvec{G}_i$ over $\mathbb{F}_q$ and the random choices for
$\myvec{G}_1,\dots,\myvec{G}_N$ are all independent.\footnote{We stress that we do
  {\em not} require that the $\myvec{G}_i$'s have rank $n$.}%
Then the concatenated code $C^*=C_{\rm out}\circ(C_{\rm in}^1,\dots,C_{\rm in}^N)$ is a
$\left(1-R-\varepsilon,\left(\frac{N}{\varepsilon^2}\right)^{O\left(\varepsilon^{-2}\log(1/R)\right)}\right)_{led}$-list
decodable code with probability at least $1-q^{-\Omega(nN)}$ over the
choices of $\myvec{G}_1,\dots,\myvec{G}_N$. Further, $C^*$ has rate $R$ w.h.p.
\end{theorem}

To set up the proof of the theorem above,
we begin by collecting certain definitions and results from~\cite{atri-venkat-soda-08}.
The following notion of independence will be crucial.

\begin{definition}[Independent tuples]
Let $C$ be a code of block length $N$ and rate $R$  defined over $\mathbb{F}_{q^k}$. Let
$J\ge 1$ and $0\le d_1,\dots,d_J\le N$ be integers. Let
$\myvec{d}=\angles{d_1,\dots,d_J}$.
An ordered tuple of codewords $(\myvec{c}^1,\dots,\myvec{c}^J)$, $\myvec{c}^j\in C$ is said
to be $(\myvec{d},\mathbb{F}_q)$-independent if the following holds.
$d_1=\textsc{wt}(\myvec{c}^1)$ and for every $1<j\le J$, $d_j$ is the number
of positions $i$ such that $c_i^j$ is $\mathbb{F}_q$-independent of the vectors
$\{c^1_i,\dots,c^{j-1}_i\}$, where $\myvec{c}^{\ell}=(c^{\ell}_1,\dots,c^{\ell}_N)$.
\end{definition}

\noindent
Note that for any tuple of codewords $(\myvec{c}^1,\dots,\myvec{c}^J)$ there exists a
unique $\myvec{d}$ such that it is $(\myvec{d},\mathbb{F}_q)$-independent. The next two results
will be crucial in the  proof of our second main result.

\begin{lemma}[\cite{atri-venkat-soda-08}]
\label{lem:frs-indp}
Let $\varepsilon>0$ and
let $C$ be a folded Reed-Solomon code of block length $N$ and rate $0<R<1$ that is defined over
$\mathbb{F}_Q$, where $Q=q^k$.
For any $L$-tuple
of codewords from $C$, where $L\ge
J\cdot (N/{\varepsilon^2})^{O\left(\varepsilon^{-1} J\log(q/R)\right)}$,
there exists a sub-tuple of
$J$ codewords such that
the
$J$-tuple is $(\myvec{d},\mathbb{F}_q)$-independent, where $\myvec{d}=\angles{d_1,\dots,d_J}$
with  $d_j\ge (1-R-\varepsilon)N$, for every $1\le j\le J$.
\end{lemma}

\begin{lemma}[\cite{atri-venkat-soda-08}]
\label{lem:frs-indp-count}
Let $C$ be a folded Reed-Solomon code of block length $N$ and rate $0<R<1$ that is defined over
$\mathbb{F}_Q$, where $Q=q^k$.
Let $J\ge 1$ and $0\le d_1,\dots,d_J\le N$ be integers and define $\myvec{d}=
\angles{d_1,\dots,d_J}$. Then the number of $(\myvec{d},\mathbb{F}_q)$-independent
tuples in $C$ is at most
\[ q^{NJ(J+1)}\prod_{j=1}^J Q^{\max(d_j-N(1-R)+1,0)} \ . \]
\end{lemma}

Given the outer code $C_{\rm out}$ and the inner codes $C_{\rm in}^i$, recall that
for every codeword $\myvec{u}=(\myvec{u}_1,\dots,\myvec{u}_N)\inC_{\rm out}$, the
codeword  $\myvec{u}\myvec{G}\stackrel{def}{=}(\myvec{u}_1\myvec{G}_1,\myvec{u}_2\myvec{G}_2,\dots,\myvec{u}_N\myvec{G}_N)$ is in $C^{*}=C_{\rm out}\circ(C_{\rm in}^1,\dots,C_{\rm in}^N)$,
where the operations are over $\mathbb{F}_q$.

We now begin with the proof.
The fact that $C^*$
has rate $R$ w.h.p. follows the argument used in~\cite{atri-venkat-soda-08} and is omitted.

Define $Q=q^k$.
Let $L$ be the worst-case list size that we are
aiming for (we will fix its value at the end). By Lemma~\ref{lem:frs-indp},
any $L+1$-tuple of $C_{\rm out}$ codewords $(\myvec{u}^0,\dots,\myvec{u}^L)\in(C_{\rm out})^{L+1}$
contains at least
$J= \left\lfloor (L+1)/(N/{\gamma^2})^{O\left(\gamma^{-1} J\log(q/R)\right)}\right\rfloor$ codewords that
form a $(\myvec{d},\mathbb{F}_q)$-independent tuple, for some $\myvec{d}=\angles{d_1,\dots,d_J}$,
with $d_j\ge (1-R-\gamma)N$ for all $1 \le j \le J$ (we will specify $\gamma$, $0<\gamma<1-R$, later).
Thus, to prove the theorem it suffices to show that with high
probability, there is no received word $\myvec{y}\in (\mathbb{F}_q\cup\{?\})^{nN}$ with $\textsc{wt}(\myvec{y})\le (1-R-\varepsilon)nN$
and $J$-tuple of codewords $(\myvec{u}^1\myvec{G},\dots,\myvec{u}^J\myvec{G})$, where
$(\myvec{u}^1,\dots,\myvec{u}^J)$ is a $J$-tuple of folded Reed-Solomon codewords
that is $(\myvec{d},\mathbb{F}_q)$-independent, such that $\myvec{u}^i\myvec{G}\simeq \myvec{y}$ for every $1\le i\le J$.
For the rest of the proof, we will call a $J$-tuple of $C_{\rm out}$ codewords
$(\myvec{u}^1,\dots,\myvec{u}^J)$ a \textit{good} tuple if it is $(\myvec{d},\mathbb{F}_q)$-independent
for some $\myvec{d}=\angles{d_1,\dots,d_J}$, where $d_j\ge (1-R-\gamma)N$ for every
$1\le j\le J$.

\iffalse
We'll use the same notation as in the previous result, modified and noted where necessary.

Again, the inner codes will have rate $1$, and we'll choose the alphabet of the outer code to be $Q=q^k=q^n$.

Here we can't use the strong independence property that we used in the last
proof, but we do have access to a weaker independence property that is strong
enough to provide good bounds.  Namely, of the final list of size $L+1$, we
can guarantee that $J$ of them will have the following column-wise independence property:

For some subset $S_i$ of segments of encoded message $C^*(m_i)$, each segment
in the subset can be treated as independent of the segments with the same
indices for all encoded messages $C^*(m_j)$, where $j < i$ in our list of size
$J$.  We'll refer to the size of this subset, $|S_i|$, as $d_i$.  The
guarantee is that for all $i$, $(1-R-\gamma)\cdot N\leq d_i\leq N$, when
$L\geq J\cdot (N/\gamma^2)^{O(\gamma^{-1}J\log(q/R))}.$  This bound comes from ~\cite[Lemma 4.1]{atri-venkat-soda-08}.
\fi

Define $\rho=1-R-\varepsilon$. Note that by the union bound, we need to show that
\begin{equation}
\label{eq:main-frs-concat}
\sum_{\substack{\myvec{y}\in(\mathbb{F}_q\cup\{?\})^{nN}\\\textsc{wt}(\myvec{y})\le \rho nN}} P_{\myvec{y}}
\le q^{-\Omega(nN)},
\end{equation}
where
\[P_{\myvec{y}}=
\sum_{\textrm{good }(\myvec{u}^1,\dots,\myvec{u}^J)\in(C_{\rm out})^J}
\mathop{\bf Pr}\limits\left[ \bigwedge_{i=1}^J \myvec{u}^i\myvec{G}\simeq \myvec{y}\right].
\]

For now fix a good tuple $(\myvec{u}^1,\dots,\myvec{u}^J)$ that is $(\myvec{d}=\langle d_1,\dots,d_J\rangle,\mathbb{F}_q)$-independent.
Define sets $S_i\subseteq [N]$ ($|S_i|=d_i$) to be the positions that are ``witnesses" to the fact that $(\myvec{u}^1,\dots,\myvec{u}^J)$ is
$(\myvec{d},\mathbb{F}_q)$-independent.

Then the probability that a particular codeword matches the unerased positions of the received word is:

\begin{equation}\label{trickery}
\mathop{\bf Pr}\limits[\myvec{u}^i\myvec{G}\simeq \myvec{y}] \leq \mathop{\bf Pr}\limits[(\myvec{u}^i\myvec{G})_{S_i} \simeq \myvec{y}_{S_i}].
\end{equation}

Further, the latter probability in inequality \eqref{trickery} is
independent of the probability for any  $j\neq i$.

To see this, let $E_i$ be the event that $(\myvec{u}^i\myvec{G})_{S_i} \simeq \myvec{y}_{S_i}$.

Then note that: $$\mathop{\bf Pr}\limits\left[\bigwedge_{i=1}^J E_i\right]=\mathop{\bf Pr}\limits\left[\bigwedge_{i=2}^J E_i\mid E_1\right]\cdot \mathop{\bf Pr}\limits[E_1].$$

As $(\myvec{u}^1,\dots,\myvec{u}^J)$ is a good tuple, this is simply:

$$=\mathop{\bf Pr}\limits\left[\bigwedge_{i=2}^J E_i\right]\cdot \mathop{\bf Pr}\limits[E_1].$$

Using induction, we get that the probability that all messages in the list match is just the product of the individual probabilities. Thus, we have:

$$\mathop{\bf Pr}\limits\left[\bigwedge_{i=1}^J \myvec{u}^i\myvec{G} \simeq \myvec{y}\right] \leq
\mathop{\bf Pr}\limits\left[\bigwedge_{i=1}^J (\myvec{u}^i\myvec{G})_{S_i} \simeq\myvec{y}_{S_i}\right] = \prod_{i=1}^J \mathop{\bf Pr}\limits[(\myvec{u}^i\myvec{G})_{S_i} \simeq \myvec{y}_{S_i}].$$

If we let $u_i$ be the number of unerased $q$-ary symbols in $\myvec{y}_{S_i}$, then since all the $\myvec{G}_i$ are independent
random matrices:

$$\mathop{\bf Pr}\limits[(\myvec{u}^i\myvec{G})_{S_i} \simeq \myvec{y}_{S_i}] = q^{-u_i} \leq q^{-d_i n + \rho n N}.$$

Note that the reason that $(-d_i n + \rho n N) \geq -u_i$ is because in
the worst case, all erasures occur in $S_i.$

We take a union bound over the number of different ways that the $d_i$ can
occur:

\begin{equation}\label{mother}
P_{\myvec{y}}\leq\sum_{(1-R-\gamma)N\le d_1,d_2,\cdots,d_J\le N} \left(q^{NJ(J+1)} \prod_{i=1}^J Q^{~\max{(0,d_i-N(1-R))}}\right)\prod_{i=1}^J q^{-d_i n + \rho n N}.
\end{equation}

The bound in parenthesis in inequality \eqref{mother} comes from Lemma~\ref{lem:frs-indp-count}.

Now since $$\max{(0,d_i-(1-R)N)} \leq d_i - (1-R-\gamma) N,$$

we can rewrite this, collapsing the two products into one, as:

\begin{equation}
\label{eq:small-r}
P_{\myvec{y}}=\sum_{(1-R-\gamma)N\le d_1,d_2,\cdots,d_J\le N} \left(q^{NJ(J+1)} \prod_{i=1}^J q^{n(d_i -(1-R-\gamma) N) - d_i n + \rho n N}\right).
\end{equation}

But since:

$$n d_i - n d_i = 0,$$

we can rewrite this again, replacing the sum with an upper bound, as

$$P_{\myvec{y}} \leq N^J q^{NJ(J+1)} q^{JnN (\rho -1 + R + \gamma)}. $$

Note that:

$$q^{NJ(J+1)} = q^{N J n \left(\frac{J+1}{n}\right)}.$$

So for $n\ge (J+1)/\gamma$:

$$q^{NJ(J+1)} \leq q^{JnN\gamma}.$$

Note also that the total number of possible received words can be bounded as follows:

\begin{equation}\label{brick}
{{nN}\choose{\rho nN}}\cdot q^{(1-\rho)nN} \leq q^{2nN},
\end{equation}

where the first term in the product on the left-hand side of inequality
\eqref{brick} is the number of ways to choose erasure locations, and the
second term is the number of ways to choose symbols in the unerased positions.

Also,

$$N^J\le q^{J\log N}\leq q^{JnN\gamma}$$

for large enough $N$.

After applying these bounds, we get that:

\begin{equation}\label{fudge}
\mathop{\bf Pr}\limits[C^*~\text{is not}~(\rho,L)_{led}] \leq q^{2nN} q^{J n N (\rho -1 +R + 3\gamma)}.
\end{equation}

Recall that we have $R=1-\rho-\epsilon$ and can choose $J$ and $\gamma$ freely.

Setting

$$J\geq 1/\gamma$$

will make

$$q^{nN} \leq q^{J n N \gamma},$$

and in particular,

$$q^{2nN} \leq q^{J n N (2\gamma)}.$$

If we pick $\gamma=\epsilon/10$, then our final
error probability in inequality \eqref{fudge} will be:

$$\mathop{\bf Pr}\limits[C^*~\text{is not}~(\rho,L)_{led}] \leq q^{-\frac{\epsilon}{2} J n N},$$

establishing the desired error bound.

\begin{remark}
It is easy to see that the rate of the inner codes have to be very close to $1$.
To see this consider the erasure pattern where $\rho$ fraction of the outer codeword
symbols are completely erased. To recover from such a situation, we need $R$ to be
close to $1-\rho$. One could re-visit the proof above for general $r$ and
try to figure out how far away from $1$ $r$ can be. If we had $r<1$ then in
(\ref{eq:small-r}), the exponent within the product should read $rn(d_i-(1-R-\gamma))-d_in+\rho nN$. We ultimately need $R^*=Rr=1-\rho-\epsilon$. Using this and some
manipulations, the exponent becomes $(1-r)(1-d_i/N)-\epsilon +r\gamma$. The only thing that we
can guarantee about $d_i$ is that $d_i\ge (1-R-\gamma)N$. If we desire the ultimate
error probability to be $q^{-\Omega(\epsilon nNJ)}$, then the proof goes
through only if $rR\ge R-O(\epsilon)$.
\end{remark}

\subsection{Random Linear Outer Code}

\begin{theorem}
\label{thm:random}
Let $q$ be a prime power and let $0<R \le 1$ be an arbitrary rational.
Let $n,K,N\ge 1$ be large enough integers such that $K=RN$.
Let $C_{\rm out}$ be a random linear code over $\mathbb{F}_{q^{n}}$
that is generated by a random $K\times N$ matrix over $\mathbb{F}_{q^n}$.
Let
$C_{\rm in}^1,\dots,C_{\rm in}^N$ be random linear codes over $\mathbb{F}_q$, where
$C_{\rm in}^i$ is generated by a random $n\times n$ matrix $\myvec{G}_i$
and the random choices for $C_{\rm out},\myvec{G}_1,\dots,\myvec{G}_N$ are
all independent. Then the concatenated code $C^*=C_{\rm out}\circ(C_{\rm in}^1,\dots,C_{\rm in}^N)$
is a $\left(1-R-\varepsilon,q^{O(1/\varepsilon^2)}\right)_{led}$-list
decodable code with probability at least $1-q^{-\Omega(nN)}$ over the choices
of $C_{\rm out},\myvec{G}_1,\dots,\myvec{G}_N$. Further, with high probability, $C^*$ has rate
$R$.
\end{theorem}

\begin{proof}
Let $q\ge 2$ and $R^{*}=R$ be the rate of the outer code (the inner
codes are chosen so that their dimension $k=n$, and therefore have rate $1$).

We define a segment of a codeword in $C^*$ as a sequence of consecutive
$q$-ary symbols generated by one particular inner code.  An assumption that
we will make for the ease of analysis (and which we will remove later) is that
erasures, which occur with relative rate $\rho$, will be equally distributed
among the concatenated codeword segments.  This means that in our received
word $\myvec{y}$, the result of each of the $N$ inner code encodings will contain
at most $\rho n$ erasures.

We will show that there exists some integer $L$ such that any subset
of $L+1$ distinct encoded messages has the property that they all match the
non-erased segments of the received word with low probability.  Then we'll
apply the union bound to show that with high probability, the code meets the
list decoding capacity for erasures.

Define $Q=q^k$ and $\rho=1-R^*-\varepsilon$.
Let $J=\lfloor \log_Q(L+1)\rfloor$.  Then there exists a subset of size at
least $J$ of our list (which is of size $L+1$) such that the set of
messages $\{\myvec{m}_1,\myvec{m}_2,...\myvec{m}_J\}$ will be linearly independent
over $\mathbb{F}_{Q}$.  This is because there are only $Q^J$ unique ways
to form linear sums of these messages over $\mathbb{F}_Q$.

Because of this fact and because $C_{out}$ is a random linear code, the set
$\{C_{out}(\myvec{m}_1),C_{out}(\myvec{m}_2),\cdots ,C_{out}(\myvec{m}_J)\}$ can be treated as a set
of independently chosen random vectors in $\mathbb{F}_{q^k}^N$.

Fix an $s$ so that $1\leq s\leq N$ and let $y_s$ represent a particular segment
of our received word.  (There are $N$ such segments over $\mathbb{F}_Q$).  In our list of $J$ outer
encoded messages, we denote by $i$ the size of the subset of these where for each
outer encoded message $C_{out}(\myvec{m}_t)$, restricted to the segment $s$, $C_{out}(\myvec{m}_t)$
is the zero vector.  $J-i$ is then the number of messages such that $C_{out}(\myvec{m}_t)$ is
not the zero vector when restricted to the segment $s$.

We can bound the probability that each of these messages match the received
word at this segment, in the unerased positions, as follows:

\begin{equation}\label{prob_match}
\mathop{\bf Pr}\limits[(C^*(\myvec{m}_t))_s \simeq y_s ]\le \left(\frac{1}{q^n}\right)^i\left(1-\frac{1}{q^n}\right)^{J-i}\cdot q^{-(1-\rho)n(J-i)}.
\end{equation}

In the above, the relationship $(C^*(\myvec{m}_t))_s \simeq y_s$ means that the concatenated
code, on message $\myvec{m}_t$, restricted to segment $s$, matches the received word
$y$ on segment $s$ at all unerased positions.

If $(C_{out}(\myvec{m}_t))_s = 0$, then we just assume that $(C^*(\myvec{m}_t))_s \simeq y_s$,
so this is an upper bound, and not an equality.

The first term in the RHS of \eqref{prob_match} is the probability that $i$ messages
at this segment map to the zero vector, and the second term is the probability
that $J-i$ messages map to something other than the zero vector.

The third term is the probability that those nonzero $J-i$ messages
match the received word in every unerased position.

Now since

$$\left(1-\frac{1}{q^n}\right)^{J-i} \leq 1,$$

we have that

$$\mathop{\bf Pr}\limits[(C^*(\myvec{m}_t))_s \simeq y_s ]\le q^{-(1-\rho)nJ}\cdot q^{i(1-\rho)n-in}.$$

Also, because $(1-\rho)$ is always less than 1,

$$q^{i(1-\rho)n-in}\le 1.$$

Therefore

$$\mathop{\bf Pr}\limits[(C^*(\myvec{m}_t))_s \simeq y_s ]\le q^{-(1-\rho)nJ}.$$

The probability, then, that every message in the list matches the
received word in the unerased positions for a single segment, taken
over all possible choices of locations and sizes of $i$ is then
(by the union bound over such locations and sizes, noting that there
are at most $q^J$ ways to make these choices):

\begin{equation}\label{collected_rho}
\mathop{\bf Pr}\limits\left[\bigwedge_{t=1}^J (C^*(\myvec{m}_t))_s \simeq y_s\right]\le q^J\cdot q^{-(1-\rho)nJ}.
\end{equation}

Recalling that each inner code is chosen independently, the probability
that this is true for all segments is then

$$\mathop{\bf Pr}\limits\left[\bigwedge_{t=1}^J C^*(\myvec{m}_t) \simeq \myvec{y}\right]\le q^{JN}\cdot q^{-(1-\rho)nJN}.$$

Taking the union bound over all possible received words and lists of size $J$:

\begin{equation}\label{final_prob}
\mathop{\bf Pr}\limits[C^*~\text{is not}~(\rho,L)_{led}]\le q^{nN}\cdot q^{(1-\rho)nN}\cdot q^{kKJ}\cdot q^{JN}\cdot q^{-(1-\rho)nJN}.
\end{equation}

The first term in RHS of \eqref{final_prob} is an upper bound on
the number of possibilities for the erasure positions.
The second term is the number of ways to specify the
unerased positions, the third term is the number of possible lists of
size $J$, and the fourth and fifth terms come from the previous inequality.

Since $kK=R^*nN$, and $2>1+(1-\rho)$, this can be rewritten and simplified as:

$$\mathop{\bf Pr}\limits[C^*~\text{is not}~(\rho,L)_{led}]\le q^{-nNJ\left(\frac{-2}{J}-R^*-\frac{1}{n}+\left(1-\rho\right)\right)}.$$

If we can choose $n$, $R^*$, and $J$ appropriately so that:

$$\frac{-2}{J} - R^* -\frac{1}{n} + (1-\rho) \ge \epsilon/2,$$

then this probability will be exponentially small.

Setting
$n\ge J, J=\lceil \frac{6}{\epsilon}\rceil$
works.

We still need to fix the assumption that the $\rho$ fraction of erasures are
all distributed equally among the $N$ encoded segments.

Note that if we describe the fraction of erasures in each segment by $\rho_s$,
then

$$\sum_{s=1}^N \rho_s n = \rho nN.$$

The per-segment probability then becomes

$$\mathop{\bf Pr}\limits[(C^*(\myvec{m}_t))_s \simeq y_s]\le q^J\cdot q^{-(1-\rho_s)nJ}$$

and the probability for the entire received word becomes

$$\mathop{\bf Pr}\limits\left[\bigwedge_{t=1}^{J} C^*(\myvec{m}_t) \simeq y\right]\le \prod_{s=1}^N q^J\cdot q^{-(1-\rho_s)nJ}.$$

Note further that the $\rho_s$ terms can be collected in the exponent
and simplified to inequality \eqref{collected_rho}.

Finally, the claim that $C^*$ has rate $R$ follows from a similar argument to that
from~\cite{atri-venkat-soda-08} and
is omitted.
\end{proof}
\subsection*{Acknowledgments} We thank Venkat Guruswami and Parikshit Gopalan for
helpful discussions. Thanks again to Madhu Sudan for kindly allowing us to include Lemma~\ref{lem:inverse-markov}
in this paper.

\bibliographystyle{abbrv}

redpajama_set_name: RedPajamaArXiv


text:
Mario Lopez Joins 'Access Hollywood' As Host
Best Buy Shares Soar On Report That Founder Is Preparing $6B Takeover Offer
The stock is up about 15% this morning after the Minneapolis-based company's home town paper, the Star Tribune, reported that founder Richard Schulze will make "a fully financed offer" of as much as $6B for Best Buy "by the end of the week, possibly on Friday." The potential offer contrasts with the $8.8B proposal Schulze made in August. But Best Buy shares have declined more than 20% since then as it reported softer than expected earnings — which CEO Hubert Joly said were "clearly unsatisfactory" — and lowered its financial forecasts. Bankers and private equity said to be backing Schulze include Cerberus, Leonard Greene & Partner and the Texas Pacific Group,. He's also working with the consumer electronics chain's former CEO Brad Anderson and former president Al Lenzmeier. Schulze, who launched the company in 1966, resigned from the board in June. That upended a face-saving deal he made with the board after its Audit Committee said in a report that Schulze helped to cover up former CEO Brian Dunn's "inappropriate relationship" with a female employee. Corporate law in Minneapolis makes it virtually impossible to mount a hostile takeover. But Schulze's relationship with the company is said to have warmed as its business performance cooled, in large part due to its inability to keep up with rivals including Amazon and Walmart. In August Best Buy gave him permission to proceed with an effort to bid for the company. That agreement allows Schulze to return with a second offer in January if the company rejects his first one. That's seems likely as part of the negotiation process.
Richard Schulze

redpajama_set_name: RedPajamaCommonCrawl


I was approached by CURIOOS and Publicis Paris as they were looking for some artists to take part in a launch campaign for BNP Paribas's new brand "Hello Bank".
The brief was simple: BNP Paribas wanted me to illustrate the word "Hello" in my very own style, the finished work just had to be dominated by the color blue. The final artwork has been used to promote the launch in online media and on various social media sites.


text:
DART transit fleet represents leadership in clean fuels
Leadership in clean fuels
In addition to introducing the Southwest's first zero-emission transit fleet of electric light rail trains, DART has aggressively pursued a clean fuels program highlighted by new transit engine technology, liquefied natural gas and the creation of the ultra-low sulfur diesel market for Texas.
Thanks to the aggressive replacement of 710 buses since 1996, the NOx (oxides of nitrogen) emissions have been reduced by 701 tons per year. In addition, emissions have been further reduced by 258 tons per year as a through-the-exhaust gas recirculation (EGR) engine retrofit project. DART bus fleet emissions prior to 1996 were approximately 1,344 tons per year. The retrofit program was made possible by a grant from the State of Texas.
The combination of more new buses and the engine retrofit on hundreds of other buses in the fleet -allow them to benefit from the use of ultra-low-sulfur diesel. The net effect of these two initiatives will reduce current bus fleet NOx emission levels to only 385 tons per year. That's good news in North Texas - an area with serious air quality problems.
The retrofitted buses, running on the ultra-low-sulfur fuel, will have emissions equal to or less than natural gas. This is an important transition phase for DART's total clean fuels program. A major goal of the program is to begin operating zero-emissions buses by the end of the decade.
When DART began using ultra-low sulfur emissions fuel earlier this decade, it had to be purchased from refiners on the east or west coasts. Now, having created a market for the fuel, DART is able to purchase this fuel from two plants in Texas. Other transit properties in the state are also adopting this clean fuel.
DART introduced liquefied natural gas fueled buses in 1998 as an initial phase of its clean fuels program. DART's use of the fuel has received national attention and has provided valuable information the agency is applying as it moves toward its goal of operating a zero-emissions bus fleet.


Most pets (read "most dogs") love going for car rides. Service Advisor Nelson Beverly and his wife Christina have a toy poodle named Scooter. When they say the word "ride" in front of Scooter he lights up as if it were Christmas morning. This month we interviewed Scooter to get his recommendations on Pet Car Safety.
Don't ever put me in the bed of a pickup truck! The Humane Society estimates that approximately 100,000 dogs are killed each year from being thrown or jumping out of a pickup. Besides, I'd so much rather sit in the air conditioned cab with you!
We may be super excited to join you for a drive, but please buckle me in. There are many Center for Pet Safety approved products that will keep me nicely contained and from roaming freely about the vehicle. Harnesses and dogs seats are life-savers. It keeps us from distracting you while driving AND reduces the risk of injury if we are involved in an accident. Also, I love you so very much but please don't allow me to ride in your lap. You need to be focused on the road and have all fingers and toes available if you need to make a sudden maneuver.
Don't leave me in the car by myself, please! It can get awfully warm in the car very quickly and the consequences are dire. Twenty-eight states, including Florida, have laws that either prohibit leaving an animal in confined vehicle under dangerous conditions or provide civil immunity (protection from being sued) for a person who rescues a distressed animal from a vehicle. To see the laws for a specific state visit https://www.animallaw.info/topic/table-state-laws-protect-animals-left-parked-vehicles.
A fresh bowl of water for longer car rides is great! A ride around the block is fine, but for those longer trips please remember to bring some fresh water along for me!
Don't let me hang my head out the window. I mean, I know I enjoy it and all those smells, but it's really not a good idea. I can easily try and jump out if I see another animal, or you never know when there could be an unexpected flying rock or even another vehicle. Just a little crack of the window is all I need to get the tease of fresh air and wind in my face.
Don't just take me to the vet when we get in the car. This is no bueno because every time we get in the car I will get all anxious and think we're headed to the vet of course! Take me around the block, to the pet store, to the park!
Don't forget to take your car to my dad's shop to make sure it's safe for the entire family!
These are just some of the main tips Scooter wanted to share with our readers, he did pretty good for not having opposable thumbs - now he has some toys to go play with and then a scheduled nap; his life is ruff.
Make sure your ride is safe for you, your family, and your furry friends!
Bring any concerns, weird noises, or flashing lights to Harrell & Beverly.


text:
Source: Universal Pictures
Michael Myers Could Haunt Us in Our Nightmares Forever — Will We See Him on the Big Screen After 'Halloween Ends'?
By Jamie Lerner
Jul. 20 2022, Published 10:16 a.m. ET
It's been five decades in the making, but Halloween Ends is finally coming to the big screen in October 2022. The final film in the spin-off Halloween trilogy that began in 2018, Halloween Ends is set to end Laurie Strode's story in the Halloween franchise. However, after almost 50 years with Michael Myers as the haunting masked villain of the films, some of us are ready to never see him again.
Michael Myers is the man who haunts many of our nightmares. Played by over 18 actors over the course of 12 films, Michael is the man who made slasher villains what they are today. There's nothing more frightening than coming across someone in a Michael Myers mask on Halloween night, and now we're wondering if Halloween Ends is the last Michael Myers movie in the franchise.
Source: Compass International Pictures
'Halloween Ends' is the final movie in the new 'Halloween' trilogy.
Everything that leads to Halloween Ends began in 1978 with the very first Halloween flick. Ignoring all other sequels since that film, the 2018 Halloween picks up where the 1978 one leaves off, forty years later.
This modern-day trilogy, which stars Jamie Lee Curtis in her original role as Laurie Strode, follows Laurie as she tries to take down Michael once and for all. However, because it ignores Halloween II, their sibling relationship that was so prevalent in many of the Halloween sequels is no longer relevant.
Despite this, there's a clear connection between Michael Myers and Laurie Strode, and Halloween Ends is set to, well, get to the end of it. Based on the trailer, it seems like it will tackle the classic trope of lifelong nemeses — only one can survive. But who will it be? Will Michael or Laurie be the ultimate survivor? Regardless of the answer, we do know that Halloween Ends is the final film in this updated trilogy, and that it is Jamie Lee Curtis's final turn as Laurie Strode.
A post shared by Jamie Lee Curtis (@curtisleejamie)
In an Instagram post from February 2022, Jamie shared, "A bittersweet end for me on the Halloween movies. I've made great friends and have collaborated with wonderful artists on these three movies, and today my part in the film has been completed and with it the end for me of this trilogy … I love this crew and cast and I will miss you all. We can't wait for the fans to see the movie." Does this mean that Laurie dies and Michael lives? Not necessarily, but that is a possibility.
It's unlikely that 'Halloween Ends' is the last Michael Myers movie.
While Halloween Ends is the last of this most recent David Gordon Green-directed trilogy, there's a very slim chance that it's the end of Michael Myers in movies. However, if Laurie defeats him in the end, it may be the end of this specific Michael. But considering the fact that there have been 12 Halloween films over the course of five decades with 10 different directors, the classic Halloween story is sure to be revived in some way.
This could mean that there will be another remake, similar to how Rob Zombie did his own revival of Halloween and Halloween II in 2007 and 2009. Or it could mean that some other director or writer will think of some other way to make the Halloween story fresh again. Between possible prequels, sequels, and spin-offs, as terrifying as it is, we may never see the end of Michael Myers.
Halloween Ends is set to release in theaters worldwide on October 14, 2022.
The House From 'A Nightmare on Elm Street' Is for Sale — Freddy Is Not Included (We Think)
We Definitely Didn't Imagine It — Laurie Strode From 'Halloween' Had a Son, Right?
[SPOILER] Falls Victim to Real-Life Serial Killer the "Night Stalker" in 'AHS: 1984'


TRAI Refuses to Bow down to Facebook on Free Basics. Here's Its Latest Letter to the Giant.
T he Telecom Regulatory Authority of India (TRAI) and Facebook don't seem to be getting along too well these days. In fact, TRAI has slammed Facebook's attempts to promote Free Basics.
A letter sent by the regulatory body to Facebook, indicates that the social media giant's recent campaign on Free Basics has not gone down well with TRAI.
Free Basics is a platform through which Facebook promises to offer a limited number of websites to people for free.
However, there are concerns that this violates the principles of net neutrality.
In the letter, TRAI has expressed its reservations about how Facebook tried to turn what was supposed to be a consultative exercise, on differential pricing of data services, into a " crudely majoritarian and orchestrated opinion poll".
Differential pricing will allow telecom companies to offer access to a few mobile apps and websites, without charging users.
Meanwhile, Facebook has accused TRAI of blocking emails people were sending, through it's website, on differential pricing – a key aspect of net neutrality.
According to TRAI, it has received around 1.89 million responses, while Facebook says more than 11 million responses supporting Free Basics has been sent to the regulatory body, say reports.
This disparity in the number of responses has become the bone of contention between TRAI and Facebook.
An open house on differential pricing of data services will be held by TRAI on January 21.
It has invited all stakeholders to participate.
It now remains to be seen if the event will lead to a consensus among the stakeholders.


Our inks are not manufactured by printer companies such as Epson, Canon, Brother or HP. The use of these names is used for clarification only.
For the Home user: High-quality dye ink.
For Photographers: Piezo Nano Chrome ink or Ultra-Chrome ink for large format printers.
Note: this kit is packed with refill ink and auto reset chipset.
Save over 95% on your printer cartridge costs with our new inotive AB refillable printer Cartridges, an alternative to CISS system the AB cartridges are much easier to fit to the new range of Epson printers.
We now stock our AB refillable printer cartridge for the new printers, with our uniquie 2 part Cartridge system you are now able to replace your used cartridges easily and quickly without having to refill all of the time. Just fill all the cartridges and once all cartridges are used then refill.
Also with our AB 2 part cartridge system you can clean the print heads without wasting any ink.
AB refillable cartridge kits come with 100ml or 120ml of each colour included.
- Cartridge capacity 14ml, 2.5 more times than normal cartridges.
- 120ml refill ink of each colour included.
- 1 Part A with auto reset chip fitted and 1 x Part B 14ml large capacity. If you want 2 or 3 B you can add it.


text:
Oorkonden van Tibetaanse gezagsdragers waren juridische getuigenissen die in opdracht van een wereldlijke of geestelijke Tibetaanse gezagsdrager werden opgesteld. Onder anderen koningen van bepaalde rijken in Tibet, zoals Guge, Ladakh, Sikkim en Mustang, en geestelijken, zoals de dalai lama, pänchen lama en karmapa, lieten zulke documenten vervaardigen.

In de oorkonden werden de inwilliging en bevestiging van bepaalde privileges, zoals belastingvrijstelling, begrazingsrecht en landbezit geregeld. Deze privileges golden voor individuen, families, kloosterorganisaties en regionale sociale groepen, zoals de Tibetaanse adel, inwoners van bepaalde plaatsen en bepaalde veetelers.

De oorkonden maakten deel uit van het Tibetaans historisch recht, naast oorkonden tussen private personen (gan rgya, khra ma), gerechtelijke schikkingen (dpyad mtshams), Tibetaanse wetten (khrims yig) en de gedragsvoorschriften in Tibetaanse kloosterorganisaties (bca' yig).

Het wetenschappelijk onderzoek naar de oorkonden maakt deel uit van de oorkondeleer.

Algemene betekenis

Tibetaanse oorkonden over vrijstelling van belastingen en afdrachten, voor overdracht van landerijen, regelingen van bezit- en dienstverhoudingen en voor de overdracht van schenkingen door de heerser zelf of zijn centrale en lokale bestuur waren in het sociale leven van de Tibetaan van essentieel belang. Geen feodaal edele of klooster was zeker van zijn landerijen of privileges, zonder dat hij het rechtmatige bezit bewees door middel van deze oorkonden.

Naast hun betekenis voor de sociale en rechtsgeschiedenis van Tibet bezitten oorkonden een bijzondere waarde als historisch bronmateriaal. De oorkonden bevatten vaak een uitvoerige narratio; dat is een formulering ofwel een oorkondedeel die de historische omstandigheid van de totstandkoming van de vergunning voor bepaalde voorrechten uiteenzet.

Verbreidingsgebied

In de tijd van de grote Tibetaanse rijk (Yarlung-dynastie; 7e-9e eeuw) en de tijd toen Tibet toebehoorde aan de heerschappij van de Yuan-dynastie (13e-14e eeuw) werd het bestuurd door een centrale regering die ook eigen oorkonden uitgaf.

In de overige periodes van zijn geschiedenis viel de Tibetaanse regio onder meerdere heerschappijen, waarvan de heersers voor het scheppen van een eigen rechtsorde met eigen kanselarijen die oorkonden uitvaardigden. Naast de tijd van de vijfde dalai lama waren het vooral de koninkrijken van Ladakh, Sikkim, Mustang en Guge die oorkonden uitvaardigden. Zelfs binnen het door Lhasa gedomineerde gebied was het gebied van de sakyaorde voldoende voorzien in autonomie, dat zijn heerser nog tot in de Nieuwe Tijd oorkonden liet uitvaardigen.

De oorkonden van al deze gebieden vertonen wat betreft hun opbouw en formulering grote overeenkomsten, waardoor men kan spreken van uniforme oorkonden in de gehele Tibetaanse regio.

Soorten
Onderscheid tussen de oorkonden in de kanselarijen van de Centraal-Tibetaanse regering (yig tshang) kwamen vooral tot uitdrukking in verschillende rechtsbetekenis.

Oorkonden waarmee de heerser in beginsel nieuwe rechtsverhoudingen creëerde, werden aangeduid als she bam. De inhoud van dergelijke oorkonden bestaat uit de toekenning van bijzondere privileges voor buitengewone verdienste. Een she bam-oorkonde kon niet door een verzoek bij de heerser verkregen worden. Ze kwam voort uit de regel van de vrije wil van de heerser, om bepaalde ambtsdragers voor hun bijzondere verdienste te belonen. Deze oorkonden werden in de regel op zijde geschreven en werden zeer zorgvuldig vervaardigd.

Gebruikelijke oorkonden werden aangeduid als bka' shog (bevelschrift) of gtan tshig (bestendige uiting). Aan deze oorkonden ging in de regel een verzoekschrift vooraf. Vaak werden ze bij de wisseling van een ambt van de heerser ter bevestiging van de bestaande rechtsverhoudingen (rgyab gnon bka' shog) verzocht en uitgevaardigd.

De regelmatige benodigde bevestigingen van bestaande rechtsverhoudingen konden door een nieuwe heerser ook door middel van eenvoudige waarmerken met een Tibetaans zegel op de overgelegde oorkonde aangebracht worden. Ze werden onder de tekst of op de rand van de ingediende oorkonde genoteerd. Ook deze, vaak zeer korte aantekeningen werden aangeduid met bka' shog.

Het plichtmatige indienen van oorkonden ter bevestiging van privileges door de nieuwe heerser bracht ook een zeker risico met zich mee. Enerzijds konden de ingediende oorkonden worden achtergehouden, wat neerkwam op het ontnemen van de privileges. Anderzijds konden met de toekenning toegestane voorrechten ook inperkingen van de verleende privileges uitgesproken worden.

Een bijzonder type oorkonden vormden de zogenoemde 'go mchan-oorkonden, dat opmerkingen bij aanvang betekent. Hier werd de juridische beschikking van de heerser direct over een ingediend verzoekschrift aangetekend dat betrekking had op rechtsgeschillen. De beschikking van de heerser kwam in de regel met de zin: "Wanneer de onderstaande uiteenzetting werkelijk waar is." De juridische betekenis van een dergelijke oorkonde was gering en kon met slechts een tegenverzoekschrift ontkracht worden.

Structuur
Tibetaanse oorkonden werden vervaardigd naar tekstueel vastgelegde formuleringsrichtlijnen die in de loop van de geschiedenis van Tibet aanzienlijke veranderingen ondergingen. In de kanselarij Yig tshang van de dalai lama werd een formuleringsboek gebruikt, dat bka' gtags 'phrin yig werd genoemd. In de regel richtten de kanselarijbeambten zich echter naar de tekst van voorhanden zijnde eerdere oorkonden. De formuleringsboeken werden er in de praktijk als naslagwerk slechts zelden bij genomen.

Bij de oorkonden zijn de volgende structurele elementen, ook intrinsieke kenmerken genoemd, te onderscheiden:
Oproep van bovenaardse machten (invocatio)
Legitimatieformuleringen (legitimatie)
Noemen van de naam of de titel van de vervaardiger (intitulatio)
Noemen van de groep mensen die van de uitvaardiging kennis moet nemen (promulgatio)
Noemen van de groep of persoon (destinair) die privileges verstrekt wordt (inscriptio)
Uitbeelding van de omstandigheden en verdienste van de destinair die tot de privileges leidden (narratio)
Uiteenzetting van de privileges die de destinair verstrekt werden (dispositio).
Strafdreiging voor het geval de in de promulgatio genoemde personen de aanwijzing van de heerser niet volgen (sanctie)
Noemen van de personen op naar aanleiding van wiens voordracht de oorkonde uitgevaardigd werd (petitio)
Noemen van de plaats en het tijdstip van de vervaardiging met een waarmerk van de vervaardiger (afsluitprotocol).

Invocatio
De oproep van bovenaardse machten (invocatio) is alleen terug te vinden in de oorkonden van de Mongoolse keizer van de Yuan-dynastie, de prinsen van het keizerlijk huis en de keizersweduwe. Twee voorbeelden hiervan zijn:

Legitimatieformuleringen

De legitimatieformuleringen worden aangetroffen in oorkonden uit de tijd van de Yuan-dynastie en drukken algemene autorisatie van de vervaardiger uit voor de afgifte door de keizer. Deze formulering heeft altijd het zinsdeel: op bevel van de keizer. Vergelijkbare formuleringen worden aangetroffen bij oorkonden van de Mongoolse koningen die onder de vijfde dalai de regeringszaken van Tibet leidden en in diverse oorkonden van Tibetaanse heersers die in de 18e en 19e eeuw uitgevaardigd werden. In zulke oorkonden is de legitimatieformulering telkens de intitulatio. Voorbeelden hiervan zijn:

Intitulatio
Het noemen van de naam of de titel van de vervaardiger (intitulatio) komt bijna bij alle oorkonden voor. Twee voorbeelden van deze formulering zijn:

Promulgatio
Bij het noemen van de groep mensen die van de uitvaardiging kennis moet nemen (promulgatio) en gevolg moeten geven aan de in de oorkonde beschikte verordeningen, richtten Tibetaanse heersers zich vaak aan alle levende wezens in de wereld. Twee voorbeelden van de promulgatio zijn:

Inscriptio
Het noemen van de groep of persoon (destinair) die privileges verstrekt wordt (inscriptio) werd vaak uitgevoerd met aan het begin de narratio. Twee voorbeelden hiervan zijn:

Narratio
De narratio is de uitbeelding van de omstandigheden en verdienste van de destinair die tot de privileges leidden. Het volgende voorbeeld toont vooral de historische waarde van veel Tibetaanse oorkonden:

Dispositio
De uiteenzetting van de privileges die de ontvanger verstrekt werden (dispositio) is vanzelfsprekend het belangrijkste deel van de oorkonde. Twee voorbeelden hiervan zijn:

Sanctie
Dreiging met straf voor het geval de in de promulgatio genoemde personen de aanwijzingen van de heerser niet volgen (sanctie) komt in de Tibetaanse oorkonden zeer veel voor. Er werd gedreigd met straf door de heerser zelf of door de transcendente beschermgoden van het Tibetaans boeddhisme. Voorbeelden zijn:

Petito
Het noemen van de personen op wier voordracht de oorkonde uitgevaardigd werd (petitio), komt alleen voor in oorkonden uit Ladakh. Een voorbeeld hiervan is:

Afsluitprotocol

Als afsluitprotocol werd algemeen afgesloten met het noemen van de plaats en het tijdstip volgens de Tibetaanse kalender. De oorkonde werd altijd bezegeld met een afdruk van de vervaardiger (eschatocol). Als waarmerk werden algemene afdrukken met een Tibetaans zegel aangebracht. In zeldzame gevallen zijn ook handafdrukken van de vervaardiger aangetroffen. Twee voorbeelden hiervan zijn:

Literatuur
 Tucci, Giuseppe (1949) Tibetan Painted Scrolls, drie delen, Rome
 Schuh, Dieter (1977) Erlasse und Sendschreiben mongolischer Herrscher für tibetische Geistliche. Ein Beitrag zur Kenntnis der Urkunden des tibetischen Mittelalters und ihrer Diplomatik, St. Augustin
 Schuh, Dieter (1981) Grundlagen tibetischer Siegelkunde. Eine Untersuchung über tibetische Siegelaufschriften in 'Phags-pa-Schrift, Sankt Augustin VGH Wissenschaftsverlag
 Everding, Karl-Heinz (2006) Herrscherurkunden aus der Zeit des mongolischen Großreiches für tibetische Adelshäuser, Geistliche und Klöster, deel 1: Diplomata Mongolica. Mittelmongolische Urkunden in 'Phags-pa-Schrift - Edition, Übersetzung, Analyse, Halle International Institute for Tibetan and Buddhist Studies
 Hanna Schneider (Bearb.): Tibetischsprachige Urkunden aus Südwesttibet (Spo-Rong, Ding-Ri und Shel-Dkar). Staatsbibliothek zu Berlin – Preussischer Kulturbesitz:
 - Band 1: Herrscherurkunden, Grundverordnungen und Generalerlasse, Konfirmationsurkunden, Rechtsentscheide, Handschreiben und schriftliche Anordnungen, Eingaben etc.. Franz Steiner: Stuttgart 2012. ISBN 978-3-515-07349-3 (Tibetische Handschriften und Blockdrucke. Teil 16).
 - Band 2: Verpflichtungserklärungen, Vergleichsurkunden, Schlichtungs- und Teilungsurkunden. Franz Steiner: Stuttgart 2012. ISBN 978-3-515-07350-9  (Tibetische Handschriften und Blockdrucke. Teil 17).

Certificaat
Economie van Tibet
Geschiedenis van Tibet
Manuscript
Schriftelijke communicatie

redpajama_set_name: RedPajamaWikipedia