Spring 2023

Lower Bounds, Learning, and Average-Case Complexity

Monday, Feb 13, 2023 to Friday, Feb 17, 2023 

Add to Calendar



Valentine Kabanets (Simon Fraser University; chair), Igor Carboni Oliveira (University of Warwick), Russell Impagliazzo (UC San Diego)

This workshop will build on recent insights about connections among complexity lower bounds, learning, and average-case complexity [Carmosino-Impagliazzo-Kabanets-Kolokolova16, Hirahara18]. Some of the major questions addressed will be: Are meta-complexity problems such as MCSP and Kpoly NP-hard, and what obstacles are there to showing hardness? Are there worst-case to average-case reductions for complexity classes such as NP and P? What are the weakest average-case hardness assumptions under which we can rule out PAC-learning of DNFs? Are restricted circuit classes such as constant-depth circuits with mod m gates (for composite m) and depth-two threshold circuits learnable efficiently under the uniform distribution?

Registration is required to attend this workshop. Space may be limited, and you are advised to register early. The link to the registration form will appear on this page approximately 10 weeks before the workshop. To submit your name for consideration, please register and await confirmation of your acceptance before booking your travel.

Further details about this workshop will be posted in due course. To contact the organizers about this workshop, please complete this form.

Please note: the Simons Institute regularly captures photos and video of activity around the Institute for use in videos, publications, and promotional materials.