Lung function measurement by optical contouring
A.R. Gourlay, G. Kaye, et al.
Proceedings of SPIE 1989
On Labor Day weekend, the highway patrol sets up spot-checks 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 spot-checking 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, convex hull, element distinctness, set containment, set equality, total orders, and correctness of group and field 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 results also give property 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).
A.R. Gourlay, G. Kaye, et al.
Proceedings of SPIE 1989
L Auslander, E Feig, et al.
Advances in Applied Mathematics
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
Martin C. Gutzwiller
Physica D: Nonlinear Phenomena