Testing of matrix properties

DOI10.1145/380752.380812MaRDI QIDQ5175981zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Ilan Newman

Publication date 27 February 2015

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

Full work available at URL https://doi.org/10.1145/380752.380812

zbMATH Keywords

matrix propertiesproperty testing

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Testing of matrix-poset properties
• scientific article; zbMATH DE number 1241385
• On the strength of comparisons in property testing
• Efficient testing of large graphs
• Three theorems regarding testing graph properties

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(19)

• Functions that have read-once branching programs of quadratic size are not necessarily testable
• A large lower bound on the query complexity of a simple Boolean function
• Testing hypergraph colorability
• Efficient removal lemmas for matrices
• Property testing for point sets on the plane
• Testing of matrix-poset properties
• Testing matrix function algorithms using identities
• Partial tests, universal tests and decomposability
• scientific article; zbMATH DE number 3843068 (Why is no real title available?)
• Testing monotonicity over graph products
• Testing graphs for colorability properties*
• Testing for forbidden posets in ordered rooted forests
• Efficient removal lemmas for matrices
• Testing local properties of arrays
• Earthmover Resilience and Testing in Ordered Structures
• Testing balancedness and perfection of linear matrices
• Property testing of curve similarity
• Property testing of the Boolean and binary rank
• Distribution-free connectivity testing for sparse graphs

This page was built for publication: Testing of matrix properties

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