The model of spot-checking, which performs only a small amount (sublinear) of additional work in order to check the program's answer, is introduced. Spot-checkers for sorting, total orders, and correctness of group operations are presented. All spot-checkers are very simple and rely on testing that the input and/or output have certain simple properties that depend of very few bits. A technique is used for testing in almost linear time whether a given operation is close to an associative cancellative operation.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1998|
|Event||Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA|
Duration: May 23 1998 → May 26 1998
ASJC Scopus subject areas