Testing linear-invariant non-linear properties

DOI10.4086/TOC.2011.V007A006MaRDI QIDQ3002831zbMATH OpenOpenAlexFDO

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

Publication date 24 May 2011

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2011.v007a006

zbMATH Keywords

Fourier analysismatroidsproperty testing

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Linear codes (general theory) (94B05)

Recommendations

• Testing linear-invariant non-linear properties
• Testing Linear-Invariant Non-linear Properties: A Short Report
• A unified framework for testing linear-invariant properties
• Testing Odd-Cycle-Freeness in Boolean Functions
• Algebraic property testing: the role of invariance

Cited in

(13)

• Testing linear operators
• Sparse affine-invariant linear codes are locally testable
• Testing Linear-Invariant Non-linear Properties: A Short Report
• Green's conjecture and testing linear invariant properties
• Control of the bilinear indicator cube testing property
• A unified framework for testing linear-invariant properties
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Testing Linear-Invariant Properties
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Testing linear-invariant non-linear properties
• Testing odd-cycle-freeness in Boolean functions
• Computing linearizations using test sets
• Testing linear inequalities of subgraph statistics

This page was built for publication: Testing linear-invariant non-linear properties

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