Testing of matrix properties

DOI10.1145/380752.380812zbMath1323.68313OpenAlexW2060706760MaRDI QIDQ5175981

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

property testingmatrix properties

Mathematics Subject Classification ID

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

Related Items (7)

Testing monotonicity over graph products ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Testing of matrix-poset properties ⋮ Testing hypergraph colorability ⋮ Testing graphs for colorability properties* ⋮ 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

Cites Work

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

This page was built for publication: Testing of matrix properties