Relationships between Self-Testing/Correcting Programs and Interactive Proofs

点击翻译按钮获取中文摘要

Even the simplest of programs can be full of elusive errors. The study of program checkers, self-testing programs and self- correcting programs was introduced in order to allow one to use a program P to compute a function f without trusting that P works correctly. Many problems are easy to specify, but efficient programs which solve them may be vepy complicated. For such problems, the proposed approaches to program correctness have already show promise. The goal of this project is to understand how broadly these techniques apply. This research will develop a core of algorithmic techniques for writing fast and simple checkers, self-correctors, and self-testers. Previous research on self-correctors and self-testers obtained theoretical tools and insights which have been used in recent results in the theory of interactive proof systems. This research involves the study of the relationships between these areas. Other topics in the area of computational learning theory and game theory will be studied. These topics have applications to algorithms in reinforcement learning, text correction, part-of-speech-tagging, DNA sequencing and handwriting recognition. Interactive activities include teaching a graduate course entitled Program Correctness Probabilistic Proof Checking and Interactive Proofs.