2-transitivity is insufficient for local testability

DOI10.1007/s00037-012-0055-3zbMath1283.94130OpenAlexW2180664492MaRDI QIDQ1947041

Madhu Sudan, Tali Kaufman, Elena Grigorescu

Publication date: 11 April 2013

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-012-0055-3

zbMATH Keywords

locally testable codesaffine invariance2-tranzitivity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Cyclic codes (94B15) Randomized algorithms (68W20)

Related Items (9)

Sparse affine-invariant linear codes are locally testable ⋮ Limitation on the Rate of Families of Locally Testable Codes ⋮ Invariance in Property Testing ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ On Sums of Locally Testable Affine Invariant Properties ⋮ Limits on the Rate of Locally Testable Affine-Invariant Codes ⋮ A unified framework for testing linear‐invariant properties ⋮ Characterizations of locally testable linear- and affine-invariant families

Cites Work

• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Self-testing/correcting with applications to numerical problems
• Graph limits and parameter testing
• On Sums of Locally Testable Affine Invariant Properties
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Succinct Representation of Codes with Applications to Testing
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• Robust Characterizations of Polynomials with Applications to Program Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• New Extension of the Weil Bound for Character Sums with Applications to Coding
• Some 3CNF Properties Are Hard to Test

This page was built for publication: 2-transitivity is insufficient for local testability