Testing of matrix properties

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property P and an input f , distinguish between the case that f satisfies P , and the case that no input that differs from f in less than some fixed fraction of the places satisfies P . An (ε,q) -test for P is a randomized algorithm that queries at most q places of an input x and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε -fraction of the places of f need to be changed in order for it to have the property.

Authors

• Eldar Fischer
• Ilan Newman

Keywords

• matrix properties
• property testing