2-transitivity is insufficient for local testability
type: Item
instance of: scholarly article
title: 2-transitivity is insufficient for local testability
zbMATH Open document ID: 1283.94130
author: Elena Grigorescu
author: Tali Kaufman
author: Madhu Sudan
published in: Computational Complexity
publication date: 2013-04-11T00:00:00Z
review text: The main goal of the paper is to prove that the following conjecture which was formulated in [\textit{N. Alon} et al., IEEE Trans. Inf. Theory 51, No. 11, 4032--4039 (2005; Zbl 1247.94057)] is not true:''The membership property in a binary error-correcting code that is \(2\)-transitive and has a small weight in its dual may be locally testable.'' The counterexample built here uses a family of affine-invariants properties defined in [\textit{T. Kaufman} and \textit{D. Ron}, SIAM J. Comput. 36, No. 3, 779--802 (2006; Zbl 1120.68058)] and a known map (trace map) early defined by Berlekamp in coding theory: \(Tr: \mathbb{F}_{q^n}\longrightarrow \mathbb{F}_q\) (\(q\) prime), \(Tr(X)=X+X^q+\dots+X^{q^{n-1}}\). The paper is an extended version of results from Elena Grigorescu's PhD thesis and from a presentation of the same authors at the 23rd IEEE conference on computational complexity in 2008. The text is very clear, more than \(50\%\) representing the proving part of the counterexample. Preliminary notions are included, making the theoretical presentation easy to follow. The paper is an important reference for those interested in studying the complexity of some algebraic property test procedures. It builds procedures for the membership property in theoretic-coding context, but I believe that they can be extended also for properties in other numerical/algebraic domains.
Mathematics Subject Classification ID: 94B15
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11T71
zbMATH DE Number: 6153144
zbMATH Keywords: affine invariance
zbMATH Keywords: locally testable codes
zbMATH Keywords: 2-tranzitivity
reviewed by: Adrian Atanasiu
MaRDI profile type: Publication
full work available at URL: s00037-012-0055-3
OpenAlex ID: W2180664492
cites work: A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
cites work: Testing Reed–Muller Codes
cites work: Proof verification and the hardness of approximation problems
cites work: Probabilistic checking of proofs
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: On Sums of Locally Testable Affine Invariant Properties
cites work: Some 3CNF Properties Are Hard to Test
cites work: Self-testing/correcting with applications to numerical problems
cites work: Graph limits and parameter testing
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Property testing and its connection to learning and approximation
cites work: Succinct Representation of Codes with Applications to Testing
cites work: New Extension of the Weil Bound for Character Sums with Applications to Coding
cites work: Testing Polynomials over General Fields
cites work: Q3549724
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
DOI: 10.1007/S00037-012-0055-3
Recommended article: Limits on the Rate of Locally Testable Affine-Invariant Codes
Recommended article: Testing Low Complexity Affine-Invariant Properties
Recommended article: Testing algebraic geometric codes
Recommended article: Succinct Representation of Codes with Applications to Testing
Recommended article: Optimal Testing of Reed-Muller Codes
Recommended article: Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
Recommended article: Sparse affine-invariant linear codes are locally testable
Recommended article: A characterization of locally testable affine-invariant properties via decomposition theorems
Recommended article: Local Testing for Membership in Lattices
Recommended article: Local Testing of Lattices
description: scientific article; zbMATH DE number 6153144