Sparse affine-invariant linear codes are locally testable

DOI10.1007/S00037-015-0115-6zbMATH Open1381.94114OpenAlexW2224258434MaRDI QIDQ2012176FDOQ2012176

Madhu Sudan, Eli Ben-Sasson, Noga Ron-Zewi

Publication date: 28 July 2017

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0115-6

Recommendations

• On Sums of Locally Testable Affine Invariant Properties
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Testing low complexity affine-invariant properties
• Every locally characterized affine-invariant property is testable
• Characterizations of locally testable linear- and affine-invariant families

zbMATH Keywords

affine invariancesum-product estimateslocally testable codesadditive combinatorics

Mathematics Subject Classification ID

Randomized algorithms (68W20) Linear codes (general theory) (94B05) Arithmetic combinatorics; higher degree uniformity (11B30)

Cites Work

• A sum-product estimate in finite fields, and applications
• Sum-product estimates applied to Waring's problem over finite fields
• Title not available (Why is that?)
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
• Some 3CNF Properties Are Hard to Test
• A combinatorial characterization of the testable graph properties
• New Extension of the Weil Bound for Character Sums with Applications to Coding
• Graph limits and parameter testing
• Algebraic property testing: the role of invariance
• A unified framework for testing linear‐invariant properties
• Every locally characterized affine-invariant property is testable
• Local list-decoding and testing of random linear codes from high error
• Succinct Representation of Codes with Applications to Testing
• Extracting Randomness Using Few Independent Sources
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Locally Testable Codes Require Redundant Testers
• 2-transitivity is insufficient for local testability
• Waring's Number in a Finite Field
• Green's conjecture and testing linear-invariant properties
• Title not available (Why is that?)
• On Sums of Locally Testable Affine Invariant Properties

Cited In (3)

• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
• Title not available (Why is that?)
• 2-transitivity is insufficient for local testability

This page was built for publication: Sparse affine-invariant linear codes are locally testable

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