On Sums of Locally Testable Affine Invariant Properties

DOI10.1007/978-3-642-22935-0_34MaRDI QIDQ3088113zbMATH OpenOpenAlexFDO

Authors Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Publication date 17 August 2011

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22935-0_34

zbMATH Keywords

direct sumserror-correcting codesproperty testingsymmetries

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Randomized algorithms (68W20)

Recommendations

• A characterization of locally testable affine-invariant properties via decomposition theorems
• Characterizations of locally testable linear- and affine-invariant families
• Characterizations of locally testable linear- and affine-invariant families
• Every locally characterized affine-invariant property is testable
• Testing low complexity affine-invariant properties
• The fundamental theorem of localizing invariants
• On affine invariant and local Loomis-Whitney type inequalities
• Local projective and affine invariants
• Some affine invariants revisited
• On free spectra of locally testable semigroup varieties

Cites work

• 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
• Graph limits and parameter testing
• Invariance in property testing
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• On locally decodable codes, self-correctable codes, and \(t\)-private PIR
• On Sums of Locally Testable Affine Invariant Properties
• On the efficiency of local decoding procedures for error-correcting codes
• Private information retrieval
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Property testing and its connection to learning and approximation
• Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
• Robust Characterizations of Polynomials with Applications to Program Testing
• Succinct Representation of Codes with Applications to Testing
• Testing low-degree polynomials over prime fields
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes

Cited in

(11)

• 2-transitivity is insufficient for local testability
• Sparse affine-invariant linear codes are locally testable
• Characterizations of locally testable linear- and affine-invariant families
• On Sums of Locally Testable Affine Invariant Properties
• Limits on the Rate of Locally Testable Affine-Invariant Codes
• From Local to Robust Testing via Agreement Testing
• A characterization of locally testable affine-invariant properties via decomposition theorems
• Correlation testing for affine invariant properties on F _p ⁿ in the high error regime
• Every locally characterized affine-invariant property is testable
• Testing low complexity affine-invariant properties
• Characterizations of locally testable linear- and affine-invariant families

This page was built for publication: On Sums of Locally Testable Affine Invariant Properties

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