Lower Bounds, Learning, and Average-Case Complexity
Organizers:
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.
