TCSDLS Speaker Biographies and Talk Abstracts 2024-2025

12:00 PM – 1:00 PM ET

Title: The Value of Errors in Proofs

Host School: Duke

Abstract: A few years ago, a group of theoretical computer scientists posted a paper on the Arxiv with the strange-looking title “MIP* = RE”, surprising and impacting not only complexity theory but also some areas of math and physics. Specifically, it resolved, in the negative, the “Connes’ embedding conjecture” in the area of von-Neumann algebras, and the “Tsirelson problem” in quantum information theory. It further connects Turing’s seminal 1936 paper which defined algorithms, to Einstein’s 1935 paper with Podolsky and Rosen which challenged quantum mechanics. You can find the paper here.

As it happens, both acronyms MIP* and RE represent proof systems, of a very different nature. To explain them, we’ll take a meandering journey through the classical and modern definitions of proof. I hope to explain how the methodology of computational complexity theory, especially modeling and classification (of both problems and proofs) by algorithmic efficiency, naturally leads to the generation of new such notions and results (and more acronyms, like NP). A special focus will be on notions of proof which allow interaction, randomness, and errors, and their surprising power and magical properties.

Biography: Avi Wigderson is the Herbert H. Maas Professor in the School of Mathematics at the Institute for Advanced Study in Princeton, New Jersey, where he has been teaching since 1999. He also served in the Computer Science Institute at the Hebrew University in Jerusalem from 1986-2003. He earned his Ph.D. in Computer Science from Princeton University in 1983. His research interests include the Computational Complexity Theory, Algorithms and Optimization, Randomness and Cryptography, Parallel and Distributed Computation, Combinatorics and Graph Theory, and Connections of CS Theory with Math and Science. Avis was the 2023 winner of the A.M. Turing Award from the Association for Computing Machinery (ACM).

4:00 PM – 5:00 PM ET

Title: Recent Developments in Succinct Proof Systems and Their Application

Host School: Duke

Abstract: In recent years succinct zero knowledge proof systems have become a very active area of research and development in both academia and industry. In this talk we will discuss a number of recent advances in the space, as well as several important applications.

Biography: Dr. Boneh is a Professor of Computer Science at Stanford University where he heads the applied cryptography group and co-directs the Computer Security Lab.  Dr. Boneh‘s research focuses on applications of cryptography to computer security.  He is the author of over 200 publications in the field and is a recipient of the 2014 ACM prize and the 2013 Godel prize.

Dates and titles are subject to change.