Spot-checkers

On Label Day weekend, the highway patrol sets up spot-checks at random poin ts on thr freeways with the intention of deterring a large fraction of moto rists from driving incorrectly. We explore a very similar idea in the conte xt of program checking to ascertain with minimal overhead that a program ou tput is reasonably correct. Our model of spot-checking requires that the sp ot-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 appl ied to problems in a wide range of areas. including problems regarding grap hs, sets, and algebra. In particular, we present spot-checkers for sorting, convex hull, clement distinctness, set containment, set equality, total or ders, and correctness of group and field operations. All of our spot-checko rs are very simple to State and rely on testing that the input and/or outpu t have certain simple properties that depend on very few bits. Our results also give proper ty tests as defined by Rubinfeld and Sudan (1996, SIAM J. Comput. 25, 252-271), Rubinfeld (1994, "Proc. 35th Foundations of Computer Science," pp. 288-299), and Goldreich et al. (1998, J. Assoc. Comput. Mach. 45, 653-750). (C) 2000 Academic Press.