This research aims to further our understanding of the interplay between randomness and computation in complexity theory. The investigation concentrates on aspects of interactive proof systems, probabilistically checkable proofs, the approximability of problems in combinatorial optimization, and related areas. One goal is to examine several ways in which construction of probabilistically checkable proofs may be improved and in so doing strengthen the derived lower bounds on approximability. In addition, a study is planned of useful structures that may be suggested by these constructions, such as error-correcting codes with novel properties. Other goals are to investigate reducibility among probabilistic constructions and to consider the possibility that there are objects that are universal for such constructions.
