5 papers
Reductions Between Code Equivalence Problems
Mahdi Cheraghchi, Nikhil Shagrithaya, Alexandra Veliche
In this paper we present two reductions between variants of the Code Equivalence problem. We give polynomial-time Karp reductions from Permutation Code Equivalence (PCE) to both Li…
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
Fernando Granha Jeronimo, Nikhil Shagrithaya
We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notion…
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…
Optimal Erasure Codes and Codes on Graphs
Yeyuan Chen, Mahdi Cheraghchi, Nikhil Shagrithaya
We construct constant-sized ensembles of linear error-correcting codes over any fixed alphabet that can correct a given fraction of adversarial erasures at rates approaching the Si…
Near-Optimal List-Recovery of Linear Code Families
Ray Li, Nikhil Shagrithaya
We prove several results on linear codes achieving list-recovery capacity. We show that random linear codes achieve list-recovery capacity with constant output list size (independe…