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

DOI10.1007/978-3-642-16367-8_18zbMath1259.68229MaRDI 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 lemma; property testing; linear invariance

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W20: Randomized algorithms

Related Items

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