| Spot-Checkers (1998) | |||||||||||||||
Abstract | |||||||||||||||
| On Labor Day Weekend, the highway patrol sets up spotchecks at random points on the freeways with the intention of deterring a large fraction of motorists from driving incorrectly. We explore a very similar idea in the context of program checking to ascertain with minimal overhead that a program output is reasonably correct. Our model of spotchecking requires that the spot-checker must run asymptotically much faster than the combined length of the input and output. We then show that the spot-checking model can be applied to problems in a wide range of areas, including problems regarding graphs, sets, and algebra. In particular, we present spot-checkers for sorting, element distinctness, set containment, set equality, total orders, and correctness of group operations. All of our spot-checkers are very simple to state and rely on testing that the input and/or output have certain simple properties that depend on very few bits. Our sorting spot-checker runs in O(log n) time to check the c... | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||