Sparse affine-invariant linear codes are locally testable

DOI10.1007/s00037-015-0115-6zbMath1381.94114OpenAlexW2224258434MaRDI QIDQ2012176

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

zbMATH Keywords

additive combinatoricssum-product estimateslocally testable codesaffine invariance

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Cites Work

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

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