On the efficiency of local decoding procedures for error-correcting codes

DOI10.1145/335305.335315zbMath1296.94171OpenAlexW1967703498MaRDI QIDQ3191974

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335315

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Decoding (94B35)

Related Items (60)

Enumerative coding for line polar Grassmannians with applications to codes ⋮ A quadratic lower bound for three-query linear locally decodable codes over any field ⋮ Can we locally compute sparse connected subgraphs? ⋮ Hermitian-lifted codes ⋮ Locality via Partially Lifted Codes ⋮ On locally decodable codes, self-correctable codes, and \(t\)-private PIR ⋮ Relative generalized Hamming weights of \(q\)-ary Reed-Muller codes ⋮ Locally Decodable Codes for Edit Distance ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ Fast systematic encoding of multiplicity codes ⋮ Improved List Decoding of Folded Reed-Solomon and Multiplicity Codes ⋮ Memory-hard puzzles in the standard model with applications to memory-hard functions and resource-bounded locally decodable codes ⋮ A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification ⋮ Succinct arguments for RAM programs via projection codes ⋮ Spanoids---An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Query-efficient locally decodable codes of subexponential length ⋮ A novel elementary construction of matching vectors ⋮ On matrix rigidity and locally self-correctable codes ⋮ Foundations of Homomorphic Secret Sharing ⋮ Lower bounds for adaptive locally decodable codes ⋮ Locally Decodable Codes: A Brief Survey ⋮ On coset leader graphs of structured linear codes ⋮ Non-interactive proofs of proximity ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ General constructions for information-theoretic private information retrieval ⋮ Short Locally Testable Codes and Proofs: A Survey in Two Parts ⋮ Local Property Reconstruction and Monotonicity ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Testability and repair of hereditary hypergraph properties ⋮ Is there an oblivious RAM lower bound for online reads? ⋮ Smooth and strong PCPs ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ Information-Theoretic Local Non-malleable Codes and Their Applications ⋮ Limitations of Local Filters of Lipschitz and Monotone Functions ⋮ Information hiding using matroid theory ⋮ High-entropy dual functions over finite fields and locally decodable codes ⋮ Locally decodable and updatable non-malleable codes and their applications ⋮ Multi-value private information retrieval with colluding databases via trace functions ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ Public Key Locally Decodable Codes with Short Keys ⋮ Short Locally Testable Codes and Proofs ⋮ Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs ⋮ On the Power of Relaxed Local Decoding Algorithms ⋮ Outlaw distributions and locally decodable codes ⋮ High-rate codes with sublinear-time decoding ⋮ An optimal lower bound for 2-query locally decodable linear codes ⋮ Lifted Multiplicity Codes and the Disjoint Repair Group Property ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Local correctability of expander codes ⋮ Some Open Problems in Information-Theoretic Cryptography ⋮ SYLVESTER–GALLAI TYPE THEOREMS FOR APPROXIMATE COLLINEARITY

This page was built for publication: On the efficiency of local decoding procedures for error-correcting codes