TY - JOUR
T1 - Spot-checkers
AU - Ergun, 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 - 1998
Y1 - 1998
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031640285&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031640285&partnerID=8YFLogxK
U2 - 10.1145/276698.276757
DO - 10.1145/276698.276757
M3 - Conference article
AN - SCOPUS:0031640285
SN - 0734-9025
SP - 259
EP - 268
JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing
T2 - Proceedings of the 1998 30th Annual ACM Symposium on Theory of Computing
Y2 - 23 May 1998 through 26 May 1998
ER -