Fall 2021

Average-Case Complexity: From Cryptography to Statistical Learning

Nov. 8Nov. 12, 2021

Add to Calendar


Luca Trevisan (Bocconi University; chair)

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. 

All events take place in the Calvin Lab auditorium.

Further details about this workshop will be posted in due course. Enquiries may be sent to the organizers workshop-si3 [at] (at this address).