[talks] CS Colloquia on making PCP practical: Friday 10/26 @ 3:30pm

[Mike Freedman]

[Mike is a systems researcher who, along with students, has been working 
on this problem with Andrew Blumberg.  Andrew is a mathematician who 
spent 2007-2008 at IAS.  So, this talk might be interesting to some 
folks on varying backgrounds.]

---

Making proof-based verified computation almost practical
Michael Walfish, The University of Texas at Austin

Friday, October 26, 2012, 3:30 PM - 4:30 PM
CS Small Auditorium (Room 105)

---

How can a machine specify a computation to another one and then, without 
executing the computation, check that the other machine carried it out 
correctly? And how can this be done without assumptions about the 
performer (replication, trusted hardware, etc.) or restrictions on the 
computation? This is the problem of _verified computation_, and it is 
motivated by the cloud and other third-party computing models. It has 
long been known that (1) this problem can be solved in theory using 
probabilistically checkable proofs (PCPs) coupled with cryptographic 
tools, and (2) the performance of these solutions is wildly impractical 
(trillions of CPU-years or more to verify simple computations).

I will describe a project at UT Austin that challenges the second piece 
of this folklore. We have developed an interactive protocol that begins 
with an efficient argument [IKO CCC '07] and incorporates new 
theoretical work to improve performance by 20+ orders of magnitude. In 
addition, we have broadened the computational model from Boolean 
circuits to a general-purpose model. We have fully implemented the 
system, accelerated it with GPUs, and developed a compiler that 
transforms computations expressed in a high-level language to 
executables that implement the protocol entities.

The resulting system, while not quite ready for the big leagues, is 
close enough to practicality to suggest that in the near future, PCPs 
could be a real tool for building actual systems.

Talk will be based on these papers and ongoing work:

http://www.cs.utexas.edu/~mwalfish/papers/ginger-usec12.pdf
http://www.cs.utexas.edu/~mwalfish/papers/pepper-ndss12.pd

---

Michael Walfish is an assistant professor in the Computer Science 
Department at The University of Texas at Austin. His research interests 
are in systems, security, and networking. His honors include an Air 
Force Young Investigator Award, an NSF CAREER Award, a Sloan Research 
Fellowship, a Teaching Excellence Award from the UT College of Natural 
Sciences, the Intel Early Career Faculty Honor Program, and the UT 
Society for Teaching Excellence. He received his B.A. from Harvard and 
his Ph.D. from MIT, both in Computer Science.