Reducing Testing Affine Spaces to Testing Linearity of Functions

DOI10.1007/978-3-030-43662-9_13MaRDI QIDQ5098778zbMATH OpenOpenAlexFDO

Authors Oded Goldreich

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-43662-9_13

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5697650
• Recovering affine linearity of functions from their restrictions to affine lines
• Testing linear-invariant function isomorphism
• Testing low complexity affine-invariant properties
• Testing Hypotheses Concerning Unions of Linear Subspaces
• Computing linearizations using test sets
• scientific article; zbMATH DE number 908022
• A unified framework for testing linear-invariant properties
• Linearity testing in characteristic two
• Linearity testing using local polynomial approximation

Cites work

• Computational Complexity
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Introduction to Property Testing
• Nearly tight bounds for testing function isomorphism
• Self-testing/correcting with applications to numerical problems
• Testing Basic Boolean Formulae
• Testing juntas
• Testing juntas nearly optimally

Cited in

(3)

• scientific article; zbMATH DE number 5697650 (Why is no real title available?)
• On one-sided testing affine subspaces
• One-sided error testing of monomials and affine subspaces

This page was built for publication: Reducing Testing Affine Spaces to Testing Linearity of Functions

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