Hal Wasserman

STOC Conference 2000 Conference Paper

Noise-tolerant learning, the parity problem, and the statistical query model

• Avrim Blum
• Adam Tauman Kalai
• Hal Wasserman

STOC Conference 1998 Conference Paper

Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound

• Mohammad Amin Shokrollahi
• Hal Wasserman

SODA Conference 1998 Conference Paper

Reconstructing Randomly Sampled Multivariate Polynomials from Highly Noisy Data

• Hal Wasserman

FOCS Conference 1994 Conference Paper

Program Result-Checking: A Theory of Testing Meets a Test of Theory

• Manuel Blum 0001
• Hal Wasserman

We review the field of result-checking, discussing simple checkers and self-correctors. We argue that such checkers could profitably be incorporated in software as an aid to efficient debugging and reliable functionality. We consider how to modify traditional checking methodologies to make them more appropriate for use in real-time, real-number computer systems. In particular, we suggest that checkers should be allowed to use stored randomness: i. e. , that they should be allowed to generate, pre-process, and store random bits prior to run-time, and then to use this information repeatedly in a series of run-time checks. In a case study of checking a general real-number linear transformation (for example, a Fourier Transform), we present a simple checker which uses stored randomness, and a self-corrector which is particularly efficient if stored randomness is allowed. >