Fall 2021

Average-Case Complexity: From Cryptography to Statistical Learning

Nov 8, 2021 to Nov 10, 2021 

Add to Calendar


Luca Trevisan (Bocconi University; chair), Boaz Barak (Harvard University), Amit Daniely (Google Research), Tselil Schramm (Stanford University), Rocco Servedio (Columbia University), Vinod Vaikuntanathan (Massachusetts Institute of Technology)

Average-case complexity has played a major role in cryptography throughout the past several decades. The interaction between cryptography and average-case problems has fueled a steady development of sophisticated ideas and techniques in pseudorandomness, worst-case to average-case hardness, interactive proofs, and many other topics. In cryptography, the primary goal is to find some distribution of problems that are computationally expensive to solve on average. In statistics, the goal is different: the aim is to understand the complexity (run-time, space and memory, communication, etc.) of problems with the natural canonical distributions, and the details of the distribution play a central role. Researchers in statistical learning theory have amassed an array of specialized probabilistic techniques and methods, which are crucial for understanding statistical estimation problems.

This workshop will bring together researchers at the forefront of statistical inference and researchers at the forefront of average-case complexity within cryptography and theoretical computer science more broadly. The goals are: (1) to foster the exchange of ideas, including advances in average case reductions in both communities, and 2) to devise appropriate and useful hardness conjectures that can aid in mapping the landscape of statistical inference problems. 

This event will be held in person and virtually. 
Please read on for important information regarding logistics for those planning to register to attend the workshop in-person at Calvin Lab.

Proof of Vaccination
Given current public health directives from state, local, and university authorities, all participants in Simons Institute events must be prepared to demonstrate proof of full vaccination: a vaccination card or photo of the card along with a valid photo ID, or a green Campus Access Badge via the UC Berkeley Mobile app (additional details regarding proof of vaccination can be found here).

Masks are required indoors for all participants regardless of vaccination status.

Light refreshments will be provided before the workshop, as well as during breaks. Please note due to current health conditions, we will set up just outside the building. There will be signs set up to direct you. Please note there is no food or drink allowed in the auditorium. Thank you for helping us to keep the auditorium clean.

If you are interested in joining this workshop, please see the Participate page.

Registration is required to attend this workshop. Space may be limited, and you are advised to register early. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.

Invited Participants: 

Anil Ananthaswamy (Journalist), Benny Applebaum (Tel-Aviv University), Boaz Barak (Harvard University), Quentin Berthet (), Quentin Berthet (University of Cambridge), Andrej Bogdanov (The Chinese University of Hong Kong), Guy Bresler (Massachusetts Institute of Technology), Joan Bruna (UC Berkeley), Amit Daniely (Hebrew University & Google), Surbhi Goel (Microsoft Research NYC), Zaid Harchaoui (University of Washington), Shuichi Hirahara (National Institute of Informatics, Tokyo), Justin Holmgren (Princeton University), Samuel Hopkins (UC Berkeley), Jun-Ting Hsieh (Carnegie Mellon University), Yuval Ishai (Technion - Israel Institute of Technology), Aayush Jain (UCLA), Sushrut Karmalkar (University of Wisconsin-Madison), Andrea Lincoln (UC Berkeley), Aditi Raghunathan (Stanford), Oded Regev (NYU), Tselil Schramm (Stanford University), Rocco Servedio (Columbia University), Nathan Srebro (Toyota Technological Institute at Chicago), Noah Stephens-Davidowitz (Cornell University), Luca Trevisan (Bocconi University, Milan, Italy), Vinod Vaikuntanathan (MIT), Xiaoqian Yang (Duke University), Ilias Zadik (Massachusetts Institute of Technology)