Testing Linear-Invariant Non-linear Properties: A Short Report

DOI10.1007/978-3-642-16367-8_18zbMath1259.68229OpenAlexW2111254285MaRDI QIDQ4933376

Madhu Sudan, Arnab Bhattacharyya, Victor Chen, Ning Xie

Publication date: 12 October 2010

Published in: Property Testing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/63125

zbMATH Keywords

regularity lemmaproperty testinglinear invariance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Related Items (3)

Universal points in the asymptotic spectrum of tensors ⋮ A polynomial bound for the arithmetic \(k\)-cycle removal lemma in vector spaces ⋮ A tight bound for Green's arithmetic triangle removal lemma in vector spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Linear equations in primes
• A combinatorial proof of the removal lemma for groups
• Self-testing/correcting with applications to numerical problems
• A removal lemma for systems of linear equations over finite fields
• Hypergraph regularity and the multidimensional Szemerédi theorem
• A Szemerédi-type regularity lemma in abelian groups, with applications
• Testing low-degree polynomials over prime fields
• Testability and repair of hereditary hypergraph properties
• Property testing and its connection to learning and approximation
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Extremal problems on set systems
• Regularity Lemma for k-uniform hypergraphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• A unified framework for testing linear‐invariant properties
• On proximity oblivious testing
• Green's conjecture and testing linear-invariant properties
• Testing Linear-Invariant Non-Linear Properties
• The counting lemma for regular k‐uniform hypergraphs

This page was built for publication: Testing Linear-Invariant Non-linear Properties: A Short Report