Spot-checkers

Funda Ergün, Sampath Kannan, S. Ravi Kumar, Ronitt Rubinfeld, Mahesh Viswanathan

Research output: Contribution to journalConference articlepeer-review

Abstract

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).

Original languageEnglish (US)
Pages (from-to)717-751
Number of pages35
JournalJournal of Computer and System Sciences
Volume60
Issue number3
DOIs
StatePublished - Jun 2000
Externally publishedYes
EventThe 30th Annual ACM Symposium on Theory of Computing - Dallas, TX, USA
Duration: May 23 1998May 26 1998

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

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

Cite this