This talk was held on Wednesday, March 01, 2017 at 7:00pm
In 1992, building on several lines of research that emerged in the 1980s and 1990s, theoretical computer scientists discovered Probabilistically Checkable Proofs (PCP). These are ways to convert claims and proofs that are time-consuming to check to ones that can be checked extremely fast. For instance, one can consider a claim like “I received 100 bitcoins a year ago and haven’t spent them,” which can be checked by going through the enormous bitcoin public ledger, and apply PCP techniques to get proofs of the claim that can be checked much faster. Interestingly, PCPs have another, completely different, motivation in theoretical computer science, which is the one that prompted the 1992 discovery: PCPs can be used to argue the hardness of even approximately solving many natural optimization problems.
In this talk, we described the different faces of PCP, the fascinating discoveries and open problems that PCP research led to, and mentioned possible practical applications.