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

Research output: Contribution to journalConference articlepeer-review


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 - 1998
Externally publishedYes
EventProceedings of the 1998 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Spot-checkers'. Together they form a unique fingerprint.

Cite this