5 papers · 1 filter
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…
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…