  In this paper, we prove that with high probability, random Reed-Solomon codes
approach the half-Singleton bound - the optimal rate versus error tradeoff for
linear insdel codes - with linear-sized alphabets. More precisely, we prove
that, for any $\epsilon>0$ and positive integers $n$ and $k$, with high
probability, random Reed--Solomon codes of length $n$ and dimension $k$ can
correct $(1-\varepsilon)n-2k+1$ adversarial insdel errors over alphabets of
size $n+2^{\mathsf{poly}(1/\varepsilon)}k$. This significantly improves upon
the alphabet size demonstrated in the work of Con, Shpilka, and Tamo (IEEE TIT,
2023), who showed the existence of Reed--Solomon codes with exponential
alphabet size $\widetilde O\left(\binom{n}{2k-1}^2\right)$ precisely achieving
the half-Singleton bound.
  Our methods are inspired by recent works on list-decoding Reed-Solomon codes.
Brakensiek-Gopi-Makam (STOC 2023) showed that random Reed-Solomon codes are
list-decodable up to capacity with exponential-sized alphabets, and Guo-Zhang
(FOCS 2023) and Alrabiah-Guruswami-Li (STOC 2024) improved the alphabet-size to
linear. We achieve a similar alphabet-size reduction by similarly establishing
strong bounds on the probability that certain random rectangular matrices are
full rank. To accomplish this in our insdel context, our proof combines the
random matrix techniques from list-decoding with structural properties of
Longest Common Subsequences.
