Lower bounds for linear degeneracy testing

DOI10.1145/1007352.1007436MaRDI QIDQ5901076zbMATH OpenOpenAlexFDO

Authors Nir Ailon, Bernard Chazelle

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.86.1190

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Lower bounds for linear degeneracy testing
• Tight bounds for testing k-linearity
• Tight lower bounds for testing linear isomorphism
• Lower bounds for adaptive linearity tests
• Low-degree test with polynomially small error
• An optimal tester for \(k\)-linear
• An optimal tester for k-Linear
• Better lower bounds on detecting affine and spherical degeneracies
• A probabilistic analysis of linear operator testing
• scientific article; zbMATH DE number 7559433

Cited in

(5)

• Better lower bounds on detecting affine and spherical degeneracies
• Low-degree test with polynomially small error
• scientific article; zbMATH DE number 910895 (Why is no real title available?)
• Lower bounds for linear degeneracy testing
• Improved algebraic degeneracy testing

This page was built for publication: Lower bounds for linear degeneracy testing

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