Spot-checkers

Funda Ergun, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan

Research output: Contribution to journalConference article

Abstract

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.

Original languageEnglish (US)
Pages (from-to)259-268
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 1998
EventProceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

    Fingerprint

ASJC Scopus subject areas

  • Software

Cite this

Ergun, F., Kannan, S., Kumar, S. R., Rubinfeld, R., & Viswanathan, M. (1998). Spot-checkers. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 259-268.