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

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

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)

Cites Work

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

Cited In (3)

• Characterizations of locally testable linear- and affine-invariant families
• Algebraic property testing: the role of invariance
• 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)