Our approach: PCPs, argument systems, and interactive proofs

Our approach is to apply the fascinating theory of Probabilistically Checkable Proofs (PCPs) and two closely related constructs: argument systems and interactive proofs.

The theory surrounding PCPs demonstrates, astonishingly, that it is possible (in principle) to check a mathematical proof by investigating only a few bits of that proof. In our context, this implies that the picture we wanted has a solution, one that is unconditional and general-purpose.

The research: make the theory practical

Unfortunately, PCPs, as described in the theoretical literature, are not remotely practical: in the most asymptotically “efficient” schemes, the server would take trillions of years to produce a proof.

Can we incorporate PCPs into a built system? So far, we have been able to come close. Here is a top-level summary of Pepper’s results to date.