New affine-invariant codes from lifting

DOI10.1145/2422436.2422494zbMath1364.94606arXiv1208.5413OpenAlexW2048651540MaRDI QIDQ2986899

Madhu Sudan, Swastik Kopparty, Alan Guo

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1208.5413

zbMATH Keywords

liftingproperty testinglocally testable codesaffine invarianceNikodym setslocally correctible codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Cyclic codes (94B15)

Related Items (18)

Finite Field Kakeya and Nikodym Sets in Three Dimensions ⋮ Hermitian-lifted codes ⋮ Locality via Partially Lifted Codes ⋮ Lifted projective Reed-Solomon codes ⋮ The minimum locality of linear codes ⋮ An algorithmic approach to entanglement-assisted quantum error-correcting codes from the Hermitian curve ⋮ Efficient proofs of retrievability using expander codes ⋮ Unnamed Item ⋮ Generic constructions of PoRs from codes and instantiations ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Unnamed Item ⋮ From Local to Robust Testing via Agreement Testing ⋮ On list decoding of certain \(\mathbb{F}_q\)-linear codes ⋮ Conical Kakeya and Nikodym sets in finite fields ⋮ High-rate codes with sublinear-time decoding ⋮ Lifted Multiplicity Codes and the Disjoint Repair Group Property ⋮ Local correctability of expander codes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: New affine-invariant codes from lifting