Characterizations of locally testable linear- and affine-invariant families

DOI10.1016/j.tcs.2011.09.030zbMath1235.94066MaRDI QIDQ764306

Yicheng Pan, Ang Sheng 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

error-correcting codes; locally testable codes; algebraic property tests

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

11T71: Algebraic coding theory; cryptography (number-theoretic aspects)

94B25: Combinatorial codes

Cites Work

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