Probabilistic Checking of Proofs
In 1992, building on several lines of research that emerged in the 1980's and 1990's, 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'll describe the different faces of PCP, the fascinating discoveries and open problems that PCP research led to, and mention possible practical applications.
Indeed is located at 6433 Champion Grandview Way Building 1 Austin, TX 78750. Please park in the garage and enter through Building 1, Floor 1 lobby.
Food and drinks will be served at 7pm. The talk will begin at 7:30pm.
Dana Moshkovitz in an associate professor at the Computer Science department of UT Austin. Her research is in Theoretical Computer Science. Much of it focuses on the limitations of approximation algorithms and probabilistic checking of proofs. Dana did her PhD at the Weizmann Institute in Israel. Her thesis co-won the Nessyahu Prize for best math PhD thesis in Israel in 2009, and part of this work was awarded the FOCS 2008 Best paper. Dana went on to spend a couple of years at Princeton University and the Institute of Advanced Study before joining MIT as an assistant professor in the end of 2010. Dana is the recipient of MIT's Jerome Saltzer teaching award.