Name: Efficient Verification of Computation with Yael Tauman Kalai
Start: 2023-05-18T18:40:00-04:00
End: 2023-05-18T20:00:00-04:00
Location: MIT Room 32-G449 (Kiva - Stata Center)

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud computing. In this talk, I will present schemes for verifying the correctness of a computation. I will discuss both their practical aspects and their impact on quantum complexity, hardness of approximation, and the complexity of Nash equilibrium.

Please register in advance for this seminar even if you plan to attend in person at
[https://acm-org.zoom.us/webinar/register/9616817586763/WN_cpY46yuPSq-LFUC5rLMZtg](https://acm-org.zoom.us/webinar/register/9616817586763/WN_cpY46yuPSq-LFUC5rLMZtg)

After registering, you will receive a confirmation email containing information about joining the webinar.

Indicate on the registration form if you plan to attend in person. This will help us determine whether the room is close to reaching capacity.

We may make some auxiliary material such as slides and access to the recording available after the seminar to people who have registered.

This is a joint meeting of the GBC/ACM ([http://www.gbcacm.org](http://www.gbcacm.org)) and the Boston Chapter of the IEEE-CS.

Peter Mager

ACM Boston

ACM Local Network

Technology

User Experience

Computer Science

High Scalability Computing

Machine Learning

Data Analytics

UX Design

Data Visualization

Predictive Analytics

Data Science

Algorithms

Deep Learning

Bernhard Suhm

Craig Herndon

Sean Carapella

Casey Hannan

Dag Holmboe

William M. Galen

Won Suh

Yael Tauman Kalai is Senior Principal Researcher at Microsoft Research New England, adjunct professor in the EECS Dept at MIT, and a member of the Computer Science and Artificial Intelligence Lab (CSAIL).

Yael works on improving the efficiency and privacy of communications through cryptography and has developed methods for verifying the correctness of computation. She developed “doubly efficient” interactive proofs that minimize the computational overhead of using strong devices, machines capable of carrying out more complex cryptographic functions. Succinct proofs offload computations from a weak device to a stronger one, paving the way for faster, more reliable transactions. Ethereum and other blockchain companies have since implemented these proofs to verify the validity of transactions. Yael’s work on delegating computation also has applications to cloud computing.

Her master’s thesis introduced the concept of ring signatures, a variation of group signatures that preserves the anonymity of individual signers, a concept she co-developed with Ron Rivest and Adi Shamir. This later became incorporated into cryptocurrency systems such as Cryptonote and Monero. Her work on the Fiat-Shamir heuristic established a better understanding of that paradigm’s security issues.

Yael graduated from the Hebrew University of Jerusalem in 1997, worked with Adi Shamir at the Weizmann Institute of Science, earning a master’s degree in 2001, and then moved to the Massachusetts Institute of Technology, where she completed her PhD in 2006 with Shafi Goldwasser as her doctoral advisor. She did postdoctoral study at Microsoft Research and the Weizmann Institute before becoming a faculty member at the Georgia Institute of Technology. She has been at Microsoft Research since 2008.

Kalai was an invited speaker on mathematical aspects of computer science at the 2018 International Congress of Mathematicians. Her master’s thesis introducing ring signatures won an outstanding master’s thesis award and her MIT PhD dissertation was awarded the George M. Sprowls Award for Outstanding PhD Thesis in Computer Science. She was co-chair of the Theory of Cryptography Conference in 2017 and chair of the Innovations in Theoretical Computer Science (ITCS) Conference in 2023. She is a fellow of the International Association of Cryptographic Research (IACR), and was recently awarded the 2022 ACM Prize in Computing “for breakthroughs in verifiable delegation of computation and fundamental contributions to cryptography”.

ACM Boston

Efficient Verification of Computation with Yael Tauman Kalai

ACM Boston

Details

Sponsors

Members are also interested in