List-Decoding with Double Samplers
From MaRDI portal
Publication:5856152
DOI10.1137/19M1276650OpenAlexW2886658624MaRDI QIDQ5856152
Irit Dinur, Inbal Livni Navon, Prahladh Harsha, Amnon Ta-Shma, Tali Kaufman
Publication date: 24 March 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/19m1276650
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Explicit constructions of Ramanujan complexes of type \(\widetilde A_d\).
- Decoding of Reed Solomon codes beyond the error-correction bound
- Laplacians and the Cheeger inequality for directed graphs
- High order random walks: beyond spectral gap
- Some remarks on multiplicity codes
- How to Play Unique Games on Expanders
- Concentration Inequalities and Martingale Inequalities: A Survey
- Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
- Linear time encodable and list decodable codes
- On uniform amplification of hardness in NP
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity
- New Direct-Product Testers and 2-Query PCPs
- Explicit, almost optimal, epsilon-balanced codes
- List Decoding of Direct Sum Codes
- Construction of new local spectral high dimensional expanders
- List Decoding with Double Samplers
- Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets
- Near-linear time decoding of Ta-Shma’s codes via splittable regularity