This workshop 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.
