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

DOI10.1007/978-3-642-16367-8_18MaRDI QIDQ4933376zbMATH OpenOpenAlexFDO

Authors Arnab Bhattacharyya, Victor Chen, Ning Xie, Madhu Sudan

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

linear invarianceproperty testingregularity lemma

Mathematics Subject Classification ID

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

Recommendations

• Testing linear-invariant non-linear properties
• Testing linear-invariant non-linear properties
• Testing Linear-Invariant Properties
• A unified framework for testing linear-invariant properties
• Nonlinearity tests
• Testing nonlinear operators
• Testing for nonlinearity using redundancies: Quantitative and qualitative aspects
• Testing linear restrictions on non-linear models
• A time-domain test for some types of nonlinearity

Cites work

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

Cited in

(8)

• 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
• Testing linear-invariant non-linear properties
• Invariance in property testing
• A unified framework for testing linear-invariant properties
• Universal points in the asymptotic spectrum of tensors
• Testing Linear-Invariant Properties
• Testing linear-invariant non-linear properties

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

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