for this workshop
Low-degree polynomial methods in average-case complexity
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.
The deadline to apply for support to participate in this workshop has passed.
For more information email workshops@aimath.org
