Fall 2021

Average-Case Complexity: From Cryptography to Statistical Learning

Nov 8, 2021 to Nov 12, 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.

Enquiries may be sent to the organizers workshop-si3 [at] (at this address).

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.