List-Decoding with Double Samplers

DOI10.1137/19M1276650MaRDI QIDQ5856152zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

Publication date 24 March 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1137/19m1276650

zbMATH Keywords

error correcting codesexpander graphshigh-dimensional expanderslist decodingpseudorandomness

Mathematics Subject Classification ID

Expander graphs (05C48) Analysis of algorithms and problem complexity (68Q25) Decoding (94B35)

Recommendations

• List decoding with double samplers
• scientific article; zbMATH DE number 1759459
• List decoding of convolutional codes
• Maximum-likelihood list decoding using trellises
• scientific article; zbMATH DE number 7650399
• List decoding in a Gaussian channel
• scientific article; zbMATH DE number 3412516
• Two theorems on list decoding (extended abstract)
• List Decoding—Random Coding Exponents and Expurgated Exponents
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

Cites work

• Concentration Inequalities and Martingale Inequalities: A Survey
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Construction of new local spectral high dimensional expanders
• Decoding of Reed Solomon codes beyond the error-correction bound
• Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
• Explicit constructions of Ramanujan complexes of type A_d.
• Explicit, almost optimal, epsilon-balanced codes
• High order random walks: beyond spectral gap
• How to Play Unique Games on Expanders
• scientific article; zbMATH DE number 1097580 (Why is no real title available?)
• scientific article; zbMATH DE number 1789922 (Why is no real title available?)
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Laplacians and the Cheeger inequality for directed graphs
• Linear time encodable and list decodable codes
• Linear-Time Encodable/Decodable Codes With Near-Optimal Rate
• List Decoding of Direct Sum Codes
• List decoding with double samplers
• List-decoding multiplicity codes
• Near-linear time decoding of Ta-Shma’s codes via splittable regularity
• New direct-product testers and 2-query PCPs
• On uniform amplification of hardness in NP
• Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets (extended abstract)
• Uniform direct product theorems: simplified, optimized, and derandomized
• Unique games on expanding constraint graphs are easy (extended abstract)

Cited in

(3)

• List decoding with double samplers
• Hardness self-amplification: simplified, optimized, and unified
• Boolean function analysis on high-dimensional expanders

This page was built for publication: List-Decoding with Double Samplers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856152)