High-rate codes with sublinear-time decoding
From MaRDI portal
Publication:5501932
DOI10.1145/2629416zbMath1321.94138OpenAlexW2024011363MaRDI QIDQ5501932
Swastik Kopparty, Sergey Yekhanin, Shubhangi Saraf
Publication date: 14 August 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2629416
polynomialsderivativeslocally decodable codeslocally correctable codessublinear-time algorithmsmultiplicity codes
Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Decoding (94B35)
Related Items (8)
Lifted projective Reed-Solomon codes ⋮ Fast systematic encoding of multiplicity codes ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives ⋮ On list decoding of certain \(\mathbb{F}_q\)-linear codes ⋮ Outlaw distributions and locally decodable codes ⋮ Lifted Multiplicity Codes and the Disjoint Repair Group Property ⋮ Simultaneous rational function reconstruction with errors: handling multiplicities and poles
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On matrix rigidity and locally self-correctable codes
- Non-deterministic exponential time has two-prover interactive protocols
- An improved lower bound on the size of Kakeya sets over finite fields
- Lower bounds for linear locally decodable codes and private information retrieval
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Query-efficient locally decodable codes of subexponential length
- Improved low-degree testing and its applications
- Pseudorandom generators without the XOR Lemma (extended abstract)
- Some remarks on multiplicity codes
- High-Rate Locally Correctable Codes via Lifting
- New affine-invariant codes from lifting
- Optimal Rate List Decoding via Derivative Codes
- Matching Vector Codes
- Proof verification and the hardness of approximation problems
- On the efficiency of local decoding procedures for error-correcting codes
- A Geometric Approach to Information-Theoretic Private Information Retrieval
- Simple extractors for all min-entropies and a new pseudorandom generator
- Towards 3-query locally decodable codes of subexponential length
- Nonlinear codes from algebraic curves improving the Tsfasman-Vladut-Zink bound
- Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- 3-query locally decodable codes of subexponential length
- Local Correctability of Expander Codes
- New generalizations of the Reed-Muller codes--I: Primitive codes
- Automata, Languages and Programming
- Locally Decodable Codes
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
This page was built for publication: High-rate codes with sublinear-time decoding
