Sparse affine-invariant linear codes are locally testable

DOI10.1007/S00037-015-0115-6MaRDI QIDQ2012176zbMATH OpenOpenAlexFDO

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

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

zbMATH Keywords

additive combinatoricsaffine invariancelocally testable codessum-product estimates

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(6)

• 2-transitivity is insufficient for local testability
• Succinct Representation of Codes with Applications to Testing
• Succinct representation of codes with applications to testing
• Explicit strong LTCs with inverse poly-log rate and constant soundness
• Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
• Testing low complexity affine-invariant properties

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)