{"id":"arxiv/2604.07234","url":"https://arxiv.org/abs/2604.07234","tags":["cs.IT","cond-mat.dis-nn","math.CO","math.PR"],"score":0,"title":"The Random Subsequence Model and Uniform Codes for the Deletion Channel","domain":"cs.IT","source":"arxiv","authors":["Ryan Jeong","Francisco Pernice"],"reviews":0,"subject":"cs.IT","summary":"We introduce the Random Subsequence Model, a spin glass model on pairs of random strings $(X,Y) \\in \\{0,1\\}^N \\times \\{0,1\\}^M$ whose partition function counts subsequence embeddings of $Y$ into $X$. We study two variants: the null model, where $X$ and $Y$ are independent and uniform, and the planted model, where $X$ is uniform and $Y$ is a uniformly-random length-$M$ subsequence of $X$. We connect the Random Subsequence Model to longstanding problems in various fields, including the best rate achievable by uniformly-random codes in the deletion channel, the longest common subsequence…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-08","reactions":{}}