Author name cluster

Jonathan Mosheiff

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

FOCS Conference 2025 Conference Paper

Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent

Matan Levi
Jonathan Mosheiff
Nikhil Shagrithaya

We establish an equivalence between two important random ensembles of linear codes: random linear codes (RLCs) and random Reed-Solomon (RS) codes. Specifically, we show that these models exhibit identical behavior with respect to key combinatorial properties—such as list-decodability and list-recoverability—when the alphabet size is sufficiently large. We introduce monotone-decreasing local coordinate-wise linear (LCL) properties, a new class of properties tailored for the large alphabet regime. This class encompasses listdecodability, list-recoverability, and their average-weight variants. We develop a framework for analyzing these properties and prove a threshold theorem for RLCs: for any LCL property $\mathcal{P}$, there exists a threshold rate $R_{\mathcal{P}}$ such that RLCs are likely to satisfy $\mathcal{P}$ when R<$R_{\mathcal{P}}$ and unlikely to do so when $R\gt R_{\mathcal{P}}$. We extend this threshold theorem to random RS codes and show that they share the same threshold $R_{\mathcal{P}}$, thereby establishing the equivalence between the two ensembles and enabling a unified analysis of list-recoverability and related properties. Applying our framework, we compute the threshold rate for list-decodability, proving that both random RS codes and RLCs achieve the generalized Singleton bound. This recovers a recent result of Alrabiah, Guruswami, and Li (2023) via elementary methods. Additionally, we prove an upper bound on the list-recoverability threshold and conjecture that this bound is tight. Our approach suggests a plausible pathway for proving this conjecture and thereby pinpointing the list-recoverability parameters of both models. Indeed, following the release of a prior version of this paper, Li and Shagrithaya (2025) used our equivalence theorem to show that random RS codes are near-optimally list-recoverable.

Details

FOCS Conference 2022 Conference Paper

Punctured Low-Bias Codes Behave Like Random Linear Codes

Venkatesan Guruswami
Jonathan Mosheiff

Random linear codes are a workhorse in coding theory, and are used to show the existence of codes with the best known or even near-optimal trade-offs in many noise models. However, they have little structure besides linearity, and are not amenable to tractable error-correction algorithms. In this work, we prove a general derandomization result applicable to random linear codes. Namely, in settings where the coding-theoretic property of interest is “local” (in the sense of forbidding certain bad configurations involving few vectors–code distance and list-decodability being notable examples), one can replace random linear codes (RLCs) with a significantly derandomized variant with essentially no loss in parameters. Specifically, instead of randomly sampling coordinates of the (long) Hadamard code (which is an equivalent way to describe RLCs), one can randomly sample coordinates of any code with low bias. Over large alphabets, the low bias requirement can be weakened to just large distance. Furthermore, large distance suffices even with a small alphabet in order to match the current best known bounds for RLC list-decodability. In particular, by virtue of our result, all current (and future) achievability bounds for list-decodability of random linear codes extend automatically to random puncturings of any low-bias (or large alphabet) “mother” code. We also show that our punctured codes emulate the behavior of RLCs on stochastic channels, thus giving a derandomization of RLCs in the context of achieving Shannon capacity as well. Thus, we have a randomness-efficient way to sample codes achieving capacity in both worst-case and stochastic settings that can further inherit algebraic or other algorithmically useful structural properties of the mother code. This is an extended abstract. The full version is available at https: //arxiv. org/abs/2109. 11725.

Details

FOCS Conference 2021 Conference Paper

Testability of relations between permutations

Oren Becker
Alexander Lubotzky
Jonathan Mosheiff

We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple (σ 1, …, σ d ) of permutations on \{1, \ldots, n\}, and one wishes to determine whether this tuple satisfies a certain system of relations E, or is far from every tuple that satisfies E. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that E is testable. For example, when d=2 and E consists of the single relation \mathrm{XY}= \mathrm{YX}, this corresponds to testing whether σ 1 σ 2 =σ 2 σ 1, where σ 1 σ 2 and σ 2 σ 1 denote composition of permutations. We define a collection of graphs, naturally associated with the system E, that encodes all the information relevant to the testability of E. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testa-bility notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability. This is an extended abstract. The full version is available at https: //arxiv. org/abs/2011. 05234. All references beyond Sections I and II refer to the full version.

Details

FOCS Conference 2020 Conference Paper

LDPC Codes Achieve List Decoding Capacity

Jonathan Mosheiff
Nicolas Resch
Noga Ron-Zewi
Shashwat Silas
Mary Wootters

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^{\ast}$ so that random linear codes of rate slightly less than $R^{\ast}$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^{\ast}$ with high probability do not. We also give a characterization of the threshold rate $R^{\ast}$. This is an extended abstract. The full version is available at https: //arxiv. org/abs/1909. 06430

Details

MFCS Conference 2013 Conference Paper

Prime Languages

Orna Kupferman
Jonathan Mosheiff

Abstract We say that a deterministic finite automaton (DFA) $\mathcal{A}$ is composite if there are DFAs $\mathcal{A}_1, \ldots, \mathcal{A}_t$ such that $L(\mathcal{A}) = \bigcap_{i=1}^t L(\mathcal{A}_i)$ and the index of every $\mathcal{A}_i$ is strictly smaller than the index of $\mathcal{A}$. Otherwise, $\mathcal{A}$ is prime. We study the problem of deciding whether a given DFA is composite, the number of DFAs required in a decomposition, methods to prove primality, and structural properties of DFAs that make the problem simpler or are retained in a decomposition.

Details