Apply for funding
for this workshop

Low-degree polynomial methods in average-case complexity

December 9 to December 13, 2024

at the

American Institute of Mathematics, Pasadena, California

organized by

Sam Hopkins, Tselil Schramm, and Alex Wein

This workshop, sponsored by AIM and the NSF, will be devoted to the study of low-degree polynomials as a restricted class of algorithms for high-dimensional statistical problems. This framework has been gaining popularity as a means to rigorously explain and predict statistical-computational tradeoffs. The workshop will focus both on new applications of the method within statistical inference, as well as potential broader implications for other areas of algorithms and computational complexity.

Topic 1:
Discover new applications of the low-degree polynomial framework, potentially beyond statistics and machine learning (e.g. circuit complexity, cryptography).
Topic 2:
Explore implications of low-degree lower bounds for other classes of algorithms (e.g. polynomial threshold functions, convex optimization).
Topic 3:
Develop new tools for low-degree lower bounds, allowing new types of problems to be analyzed.

This event will be run as an AIM-style workshop. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.

Space and funding is available for a few more participants. If you would like to participate, please apply by filling out the on-line form no later than July 9, 2024. Applications are open to all, and we especially encourage women, underrepresented minorities, junior mathematicians, and researchers from primarily undergraduate institutions to apply.

Before submitting an application, please read the description of the AIM style of workshop.

For more information email

Plain text announcement or brief announcement.