Introduction
This document serves as a curated "year-in-review" of 15 significant open problems in mathematics and theoretical computer science, compiled by researchers at ETH Zürich. Originally discussed on the Randomstrasse101 blog, this collection bridges the gap between informal online mathematical discourse and stable academic referencing. The problems highlighted represent the current frontiers of research in probability theory, high-dimensional geometry, and computational complexity, where traditional tools like concentration of measure and semidefinite programming (SDP) reach their limits.
High-Dimensional Geometry: The Ellipsoid Fitting Problem
One of the central geometric challenges discussed is the ability to "fit" random points with simple shapes. Specifically, the problem asks: given $n$ random points in $d$ dimensions, under what conditions can they be enclosed by an ellipsoid $\mathcal{E}$ that is close to the unit sphere $\mathcal{S}^{d-1}$?
Research suggests a sharp phase transition at the $d^2/4$ threshold. If $n < d^2/4$, it is conjectured that an ellipsoid can typically be fitted to the points; however, if $n > d^2/4$, such a fit becomes impossible. While Theorem 3.2 establishes a satisfiability transition for ellipsoids with bounded spectral norms, a significant gap remains: the best current upper bound for the number of points is roughly $d^2/2$, twice the conjectured threshold.
Discrepancy Theory and the Matrix Spencer Conjecture
In the realm of discrepancy theory, the "Matrix Spencer" conjecture remains a "holy grail." The problem involves finding the optimal way to sign or color elements to minimize imbalance. A key insight emerging from 2024 is the "Commutativity Gap." While mathematicians understand extreme cases—where matrices either commute perfectly or are completely non-commutative (free)—the difficulty lies in the middle ground. Recent progress has resolved the conjecture for low-rank matrices, but the general $n \times n$ case remains unsolved.
Statistical Physics, Sampling, and Synchronization
Several entries explore the intersection of algorithms and physical models:
- Sampling from the SK Model: Researchers are investigating how fast algorithms like Glauber Dynamics can sample from the Sherrington-Kirkpatrick (SK) model. Modern techniques like stochastic localization are being used to improve algorithmic bounds by leveraging the symmetry of the interaction matrix's spectrum.
- Synchronization: The conditions under which coupled oscillators spontaneously sync are being refined. While Conjecture 4 regarding global synchrony with negative edges was recently answered by McRae (2025), broader questions about the limits of synchronization in complex networks persist.
- Tensor PCA: This problem highlights the "statistical-to-computational gap." In many high-dimensional settings, a solution is mathematically proven to exist (statistical possibility), but no known polynomial-time algorithm can find it (computational hardness). The Kikuchi Free Energy hierarchy is currently being used to probe these limits.
Recent Breakthroughs and Future Work
Though these problems are defined as "open," the field is moving rapidly. Beyond McRae's 2025 result on synchronization, Conjecture 13 regarding Hadamard matrix discrepancy was recently disproven by Buhai (2025). These updates underscore the document's purpose: to define the finish line for the next generation of researchers. The primary challenge for 2025 and beyond remains closing the massive computational gaps in tensor analysis and reaching the conjectured $d^2/4$ threshold in geometric fitting.
Summary updated