Metric Testing: A Characterization of One-Sided TestabilityResearch Paper
A matrix can be too large to inspect completely even when the property being tested is defined on small collections of its labels. A one-sided tester must accept every valid matrix with probability one while finding a violation with probability at least two thirds whenever repairing the matrix requires a fixed positive fraction of its entries to change. The…