Spot-Checkers - это разновидность тестеров, проверяющих корректность работы программы. Более формально, spot-checker для функции \(P\) - алгоритм, принимающий вход \(x\) и \(f(x)\) и тестирующий близость \(f(x)\) к \(P(x)\) за сублинейное от \(|x| + |f(x)|\) время.

На докладе мы разберем spot-checkers для некоторых из следующих задач: sorting, convex hull, element distinctness, set containment, set equality, total orders, and group and field operations.