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

Please join our good friends at ACM Boston for a talk with Yael Tauman Kalai, ACM Prize in Computing 2022 Recipient.

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.

Note: You must register with Zoom before the live remote broadcast. After RSVP'ing on Meetup the Zoom link will become available.

This is a joint meeting of the GBC/ACM and the Boston Chapter of the IEEE-CS.

ACM Pittsburgh

ACM Local Network

Technology

User Experience

Machine Learning

Data Visualization

Data Analytics

Data Science

Predictive Analytics

Interaction Design

UX Design

High Scalability Computing

Mobile User Experience

Artificial Intelligence

Computer Science

User Research

Algorithms

Deep Learning

Don Krieger

Karl Herleman

Savannah Butler

Tammy

Qiyi Zhang

Prati

Rob Burton

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”.

Yael Tauman Kalai

Efficient Verification of Computation with Yael Tauman Kalai

Online event

Share this event

Efficient Verification of Computation with Yael Tauman Kalai

Details

Sponsors

ACM

Sponsors

ACM