On Sums of Locally Testable Affine Invariant Properties

DOI10.1007/978-3-642-22935-0_34zbMath1343.68287OpenAlexW2171684223MaRDI QIDQ3088113

Ghid Maatouk, Eli Ben-Sasson, Madhu Sudan, Amir Shpilka, Elena Grigorescu

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_34

zbMATH Keywords

direct sumssymmetrieserror-correcting codesproperty testing

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Randomized algorithms (68W20)

Related Items (5)

2-transitivity is insufficient for local testability ⋮ Sparse affine-invariant linear codes are locally testable ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ From Local to Robust Testing via Agreement Testing

Cites Work

• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• 2-transitivity is insufficient for local testability
• A combinatorial characterization of the testable graph properties
• Graph limits and parameter testing
• Testing low-degree polynomials over prime fields
• On Sums of Locally Testable Affine Invariant Properties
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Private information retrieval
• On the efficiency of local decoding procedures for error-correcting codes
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Succinct Representation of Codes with Applications to Testing
• Probabilistic checking of proofs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Invariance in Property Testing
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Unnamed Item

This page was built for publication: On Sums of Locally Testable Affine Invariant Properties