TY - JOUR
T1 - Spot-checkers
AU - Ergün, Funda
AU - Kannan, Sampath
AU - Kumar, S. Ravi
AU - Rubinfeld, Ronitt
AU - Viswanathan, Mahesh
N1 - Funding Information:
1This work was supported by ONR N00014-97-1-0505, MURI. 2E-mail: fergun saul.cis.upenn.edu. 3E-mail: kannan central.cis.upenn.edu. Supported by NSF Grants CCR 96-19910 and CCR 98-20885. 4E-mail: ravi almaden.ibm.com. Supported by DARPA AF F30602-95-1-0047. 5E-mail: ronitt cs.cornell.edu. Supported by NSF Career Grant CCR-9624552 and Alfred P. Sloan Research Award. 6E-mail: maheshv gradient.cis.upenn.edu. Supported by ARD DAAH04-95-1-0092.
PY - 2000/6
Y1 - 2000/6
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=0034207120&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0034207120&partnerID=8YFLogxK
U2 - 10.1006/jcss.1999.1692
DO - 10.1006/jcss.1999.1692
M3 - Conference article
AN - SCOPUS:0034207120
SN - 0022-0000
VL - 60
SP - 717
EP - 751
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 3
T2 - The 30th Annual ACM Symposium on Theory of Computing
Y2 - 23 May 1998 through 26 May 1998
ER -