Average-Case Complexity: From Cryptography to Statistical Learning

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

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



Refreshments

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.