6 papers
From Random Quantum Codes to Explicit qLDPC Codes via Local Properties
Fernando Granha Jeronimo, Xiaojuan Ma, Nikhil Shagrithaya
Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging s…
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…
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…
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…
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…