Program Checkers for Algebraic Problems

In this thesis we explore a model of ensuring the correctness of results produced by programs. This model, called program checking, is distinct from the two methods in the literature--testing and verification. Testing does not provide mathematical guarantees on the correctness of computation. Verification requires going into the inner workings of a program to determine its correctness, and is infeasible to implement for all but very simple programs.Program checking treats the programs as a black box. In the checking scenario the program is run on the desired input and the output is checked by a program checker. The checker is allowed to make other calls to the program to ensure the correctness of the original computation with very high probability. The theory of program checking draws heavily from the theory of interactive proof systems and probabilistic algorithms, but the model is intended to be very practical as well.Our focus in this thesis is on program checkers for algebraic problems. The unifying theme amongst such problems is the concept of random self-reducibility. A function (f) is randomly self-reducible if the computation of f(x) for any (x) can be reduced to the computation of several "randomly chosen" inputs. For most of the algebraic problems considered in this thesis the checkers use the fact that the problem is at least partially self-reducible. This allows us to construct sets of instances whose answers are related. Verifying consistency of the program's answers on these instances allows us to design checkers for problems in linear algebra such as rank and determinant and for problems such as graph isomorphism and group intersection.We also study the connection between interactive proofs and program checking. Using the two step approach of designing an interactive proof and converting it into a checker, we design a checker for group intersection. We construct bounded round interactive proofs for a few other problems including the problem of permutation group non-isomorphism. This interactive proof uses interesting consequences of the classification of finite simple groups.Finally we consider the notion of random self-reducibility in its own right and obtain negative results about the random self-reducibility of certain functions.

ICSI Technical Report TR-89-064

Technical Report