Characterizations of locally testable linear- and affine-invariant families

DOI10.1016/J.TCS.2011.09.030zbMATH Open1235.94066OpenAlexW1998063107MaRDI QIDQ764306FDOQ764306

Authors Yicheng Pan, Angsheng Li

Publication date 13 March 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2011.09.030

zbMATH Keywords

locally testable codeserror-correcting codesalgebraic property tests

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Combinatorial codes (94B25)

Recommendations

• Characterizations of locally testable linear- and affine-invariant families
• Algebraic property testing: the role of invariance
• On Sums of Locally Testable Affine Invariant Properties
• Every locally characterized affine-invariant property is testable
• Testing low complexity affine-invariant properties

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• 2-transitivity is insufficient for local testability
• A combinatorial characterization of the testable graph properties, it's all about regularity
• Algebraic property testing: the role of invariance
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Graph limits and parameter testing
• Improved low-degree testing and its applications
• Linearity testing in characteristic two
• Locally testable codes and PCPs of almost-linear length
• New generalizations of the Reed-Muller codes--I: Primitive codes
• On the Robustness of Functional Equations
• Probabilistic checking of proofs
• Property testing and its connection to learning and approximation
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Robust Characterizations of Polynomials with Applications to Program Testing
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Self-testing/correcting with applications to numerical problems
• Simple analysis of graph tests for linearity and PCP
• Some 3CNF Properties Are Hard to Test
• Sub-constant error low degree test of almost-linear size
• Testing low-degree polynomials over prime fields

Cited in

(3)

• Algebraic property testing: the role of invariance
• Characterizations of locally testable linear- and affine-invariant families
• On Sums of Locally Testable Affine Invariant Properties

This page was built for publication: Characterizations of locally testable linear- and affine-invariant families

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