Some Result Checkers

Checkers:

• Longest Common Subsequence
• Depth First Search
• All Pairs Shortest Path
  • Deterministic, Integral weights
  • Las Vegas, Integral weights
  • Floating-point weights
• Matrix Multiplication (Bootstrap-, Freivalds-, and Bottleneck-based Self-Testers)
• Fast Fourier Transform
  • Native-, and Bottleneck-based Self-Testers)
  • With Bug -- Illustration

Relevant Papers:

• Funda Ergun, S Ravi Kumar, and D Sivakumar. ``Self-Testing without the generator bottleneck.'' Manuscript.
• Ronitt Rubinfeld. ``Designing checkers for programs that run in parallel.'' Algorithmica, 15(4):287-301, April 1996.
• Ronitt Rubinfeld. ``A Mathematical Theory of Self-Checking, Self-Testing and Self-Correcting Programs'' , PhD Thesis, U.C. Berkeley, August 1990. ICSI Technical Report No. TR-90-054.