📊 statistics

Randomstrasse101: Open Problems of 2025

This manuscript serves as a stable academic record of the open problems in mathematics, particularly in probability, computation, combinatorics, and statistics, that were posted on the Randomstrasse101 blog during 2025.

Original authors: Afonso S. Bandeira, Daniil Dmitriev, Kevin Lucca, Petar Nizić-Nikolac, Almut Rödder

Published 2026-04-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Afonso S. Bandeira, Daniil Dmitriev, Kevin Lucca, Petar Nizić-Nikolac, Almut Rödder

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of mathematicians at a prestigious Swiss university (ETH Zurich) who run a blog called Randomstrasse101. Think of this blog as a "Mathematician's Coffee Shop" where they gather to chat about the hardest, most puzzling riddles in their field. They don't just talk about the famous, solved problems; they focus on the ones that keep them up at night, the ones that seem simple but refuse to crack.

This document is a "stable record" or a printed menu of the sixteen most interesting riddles they discussed in 2025. It's written in a friendly, informal style, meant to inspire anyone curious about how the universe of numbers and shapes works.

Here is a breakdown of the main "riddles" (Open Problems) discussed in the paper, explained with everyday analogies:

1. The "Spaghetti Tangle" (Tensor Concentration)

The Problem: Imagine you have a bunch of complex, multi-dimensional shapes (called tensors) and you shake them up randomly. You want to know: "How big can this random mess get?"
The Analogy: Think of a bowl of spaghetti. If you have one strand, it's easy to measure. If you have a million strands tangled together, it's hard to predict the size of the whole clump. The authors are trying to find a rule that predicts the maximum size of this "clump" no matter how complex the shapes are. They suspect there's a simple formula, but proving it is like trying to untangle a knot without pulling the wrong end.

2. The "Mystery Party" (Lovász Number of Random Graphs)

The Problem: In graph theory, a "graph" is a set of dots (people) connected by lines (friendships). Two big questions are: "What's the biggest group of people who all know each other?" (Clique) and "What's the minimum number of colors needed to paint them so no friends share a color?" (Chromatic number).
The Analogy: Imagine a party where everyone is either a friend or a stranger. The "Lovász number" is a clever mathematical shortcut that gives you a good guess for the answers to those questions without having to check every single person. The authors are asking: "If we throw a completely random party, how accurate is this shortcut?" They suspect the shortcut is almost perfect, but they can't prove it yet.

3. The "Blind Photographer" (Phase Retrieval)

The Problem: Imagine you take a photo, but your camera only records the brightness of the pixels, not the color or the phase (the timing of the light waves). Can you reconstruct the original picture from just the brightness?
The Analogy: It's like trying to guess a song just by listening to the volume of the music, ignoring the melody and rhythm. The authors are investigating exactly how many "brightness measurements" you need to be 100% sure you can rebuild the original image. They have a guess about the number, but a clever counter-example proved their first guess wrong, and now they are hunting for the new, correct rule.

4. The "Perfect Grid" (Mutually Unbiased Bases & Zauner's Conjecture)

The Problem: In quantum physics, you need to measure particles in different ways. Ideally, you want measurement tools that are completely "unbiased" against each other—meaning knowing the answer to one question tells you absolutely nothing about the answer to another.
The Analogy: Imagine trying to describe a 3D object. You can look at it from the front, the side, and the top. If these views are "unbiased," looking at the front gives you zero clues about what the side looks like. The authors are asking: "Is it possible to create a perfect set of these views for a 6-dimensional object?" They suspect the answer is "No," but proving it is like trying to prove a specific puzzle piece cannot fit into a hole without actually trying every possible angle.

5. The "Secret Club" (Paley Graphs)

The Problem: There is a special type of graph called a Paley Graph, built using number theory rules. It looks random, but it's actually built with a strict formula. The question is: "How big is the biggest 'secret club' (clique) inside this graph?"
The Analogy: Imagine a city where people are friends based on a secret mathematical code. Even though the city looks chaotic, the authors suspect the biggest group of mutual friends is surprisingly small (only a tiny fraction of the city). They are testing different mathematical "magnifying glasses" (like Sum-of-Squares) to see if they can prove this small size, which would help us understand how "random" these structured graphs really are.

6. The "Shape of Probability" (The KLS Conjecture)

The Problem: This is about how "bottlenecked" a shape is. Imagine a dumbbell shape. If you want to get from one weight to the other, you have to squeeze through a thin handle. This is a "bottleneck."
The Analogy: The authors are studying "convex" shapes (like a smooth ball or a cube) that don't have thin handles. They want to prove that for any such shape, no matter how high-dimensional it is, it's always easy to get from one side to the other. If you can prove this, it means you can efficiently sample random points from these shapes, which is crucial for computer algorithms that solve complex optimization problems.

7. The "Magic Matrix" (Sharp Bounds for Graph Matrices)

The Problem: When computers try to solve hard problems, they often use a method called "Sum-of-Squares." This method creates a giant grid of numbers (a matrix) to help find the answer.
The Analogy: Think of this matrix as a giant, noisy drum. When you hit it, it vibrates. The "vibration" (spectrum) tells you if the computer's guess is good or bad. The authors are trying to predict exactly how loud the drum will vibrate based on the shape of the drum. If they can predict the volume perfectly, they can tell computers exactly how hard a problem is to solve, saving them from wasting time on impossible tasks.

Why Does This Matter?

You might wonder, "Who cares about these abstract riddles?"

Cryptography: Some of these problems relate to how secure our digital codes are.
Artificial Intelligence: Understanding how to optimize complex shapes helps train better AI.
Physics: The "blind photographer" and "perfect grid" problems are directly used in quantum computing and imaging.

In short: This paper is a collection of "Wanted" posters for the most elusive mathematical truths. The authors are saying, "We have a strong hunch about the answer, but we need a brilliant mind to prove it." They invite the world to come solve these puzzles.

Based on the manuscript "Randomstrasse101: Open Problems of 2025" by Afonso S. Bandeira et al., here is a detailed technical summary.

Overview

This manuscript serves as a stable, citable record of sixteen open problems posted in 2025 on the blog Randomstrasse101, maintained by researchers at ETH Zürich and the University of Pennsylvania. The collection focuses on Probability Theory, Computation, Combinatorics, and Statistics. Rather than a traditional research paper presenting a single solved theorem, it is a curated compilation of conjectures, open questions, and recent partial results intended to guide future research. The problems span high-dimensional geometry, random matrix theory, graph theory, and optimization.

Detailed Problem Summaries by Entry

1. Tensor Concentration Inequalities (Entry 8)

Problem: Determining upper bounds for the expected supremum of a Gaussian process defined by symmetric tensors $T_i$ . Specifically, bounding $E[\|\sum g_i T_i\|_{I_p}]$ , where $g_i$ are i.i.d. Gaussians and $\|\cdot\|_{I_p}$ is the symmetric injective $\ell_p$ norm.
Methodology & Context: The authors analyze the overlap between coding theory, PDEs, and Banach space geometry. They utilize Dudley's entropy integral, which relates the expected supremum to the covering numbers of the unit ball under a specific distance metric.
Key Conjecture (Conjecture 16): For $p \ge 2$ , the expectation is bounded by $\tilde{O}_{r,p}(d^{1/2 - 1/p} \sqrt{\sum \|T_i\|_{I_p}^2})$ .
Status: Proven for $p \ge 2r$ using covering number estimates. The case $p < 2r$ remains open due to volumetric barriers. Recent work by Aden-Ali and Boedihardjo has improved bounds for specific cases (e.g., independent entries), but the general conjecture remains elusive.

2. Lovász Number of Random Circulant Graphs (Entry 9)

Problem: Characterizing the asymptotic behavior of the Lovász number $\vartheta(G)$ for random dense circulant graphs.
Methodology: The authors leverage the fact that circulant graphs are Cayley graphs over cyclic groups, allowing their adjacency matrices to be diagonalized by the Discrete Fourier Transform (DFT). This transforms the Semidefinite Programming (SDP) definition of $\vartheta(G)$ into a Linear Program (LP) in the frequency domain.
Key Conjecture (Conjecture 18): For a random dense circulant graph $G$ , $E[\vartheta(G)] = (1+o(1))\sqrt{n}$ . This mirrors the behavior of Erdős-Rényi graphs $G(n, 1/2)$ .
Results: Partial progress in [BBD+25] provides a lower bound and an upper bound of $O(\sqrt{n} \log \log n)$ using the Restricted Isometry Property (RIP) of subsampled DFT matrices.

3. Injectivity and Stability of Phase Retrieval (Entry 10)

Problem: Determining the conditions under which a matrix $A$ allows for the injective recovery of a vector $x$ from magnitude measurements $|Ax|$, and the stability of this recovery.
Methodology: The text reviews the Complement Property (necessary and sufficient for injectivity over $\mathbb{R}$ ) and introduces the quantity $\omega(A)$ , related to the condition number of submatrices.
Key Conjectures:
- Conjecture 19: Over $\mathbb{C}$ , $N=4M-5$ measurements are insufficient for injectivity with high probability (refining the $4M-4$ conjecture).
- Conjecture 20 (Balan-Wang): Relates the stability constant $\omega(A)$ to the maximum row norm of $A$ via a power law $\|A_k\|^\beta$ .
Open Question: Determining the exact value of $\omega(A)$ for Gaussian matrices and the exponent $\beta$ .

4. Mutually Unbiased Bases (MUBs) and Zauner's Conjecture (Entry 11)

Problem: The existence of Mutually Unbiased Bases in dimension $d=6$ and the existence of Symmetric Informationally Complete Positive Operator-Valued Measures (SIC-POVMs) for all dimensions.
Methodology: The entry discusses Sum-of-Squares (SoS) hierarchies as a potential tool to prove non-existence results. It also connects these problems to Equiangular Tight Frames (ETFs).
Key Conjectures:
- Conjecture 22: $MUB(6) < 7$ (i.e., 7 MUBs do not exist in $\mathbb{C}^6$ ).
- Conjecture 24 (Zauner's Conjecture): SIC-POVMs (ETFs with $n=d^2$ ) exist for all dimensions $d$ .
Status: Recent conditional proofs for Zauner's conjecture rely on number-theoretic conjectures (Stark Conjectures). An unconditional proof remains open.

5. Clique Number of the Paley Graph (Entry 12)

Problem: Bounding the clique number $\omega(G_p)$ of Paley graphs, which are deterministic graphs exhibiting pseudo-random properties.
Methodology: The authors explore convex relaxations (Lovász theta function) and localization techniques (induced subgraphs). They also consider higher-degree Sum-of-Squares (SoS) relaxations.
Key Conjectures:
- Conjecture 25: $\omega(G_p) = O(\text{polylog}(p))$ .
- Conjecture 28: Degree-4 SoS relaxation can improve the bound to $O(p^{1/2 - \epsilon})$ .
- Conjecture 29: The Paley ETF construction satisfies the Restricted Isometry Property (RIP) beyond the square-root bottleneck.

6. The KLS Conjecture and Implications (Entry 13)

Problem: The Kannan-Lovász-Simonovits (KLS) Conjecture posits that for any log-concave measure, the isoperimetric constant is bounded below by a dimension-independent constant (attained by half-spaces).
Methodology: The entry reviews the evolution of lower bounds using stochastic localization (Eldan) and bootstrapping arguments.
Key Results & Connections:
- Current Best Bound: $\psi_n \ge C (\log n)^{-1/2}$ (Klartag, 2023).
- Implications: The KLS conjecture implies the Thin Shell Conjecture (proven by Klartag and Lehec in 2025) and Bourgain's Slicing Problem (also proven in 2025).
- Significance: A positive resolution would imply optimal mixing times ( $\tilde{O}(n^2)$ ) for ball walk MCMC algorithms on convex bodies.

7. Sharp Bounds for Graph Matrices (Entry 14)

Problem: Establishing sharp spectral norm bounds for Graph Matrices, which arise in the analysis of Sum-of-Squares (SoS) lower bounds for problems like Planted Clique.
Methodology: The authors frame graph matrices as instances of Matrix Chaoses (polynomials of random variables). They utilize iterated non-commutative Khintchine inequalities and free probability tools.
Key Conjecture (Conjecture 31): The expected spectral norm of a graph matrix $M_\alpha$ scales as $\Theta(n^{f(\alpha)} (\log n)^{g(\alpha)})$ , where $f$ and $g$ depend only on the shape $\alpha$ .
Significance: Removing unnecessary polylogarithmic factors in these bounds is crucial for tightening SoS lower bounds and understanding the limits of polynomial-time algorithms.

Key Contributions and Significance

Synthesis of Interdisciplinary Frontiers: The manuscript bridges gaps between high-dimensional probability, convex geometry, quantum information theory, and theoretical computer science. For instance, it connects the geometry of log-concave measures (KLS) to the performance of MCMC algorithms and the resolution of the Slicing Problem.
Standardization of Open Problems: By compiling these problems into a stable manuscript, the authors provide a unified reference point for the community, moving away from transient blog posts to a citable academic record.
Highlighting Recent Breakthroughs: The text explicitly notes the resolution of the Thin Shell Conjecture and Bourgain's Slicing Problem in 2025, demonstrating the rapid progress in high-dimensional convex geometry and its deep connection to the KLS conjecture.
Methodological Shifts: The entries highlight a shift in methodology:
- From classical spectral methods to stochastic localization and matrix chaos theory.
- From simple SDP relaxations to higher-degree Sum-of-Squares hierarchies to break barriers in combinatorial problems (e.g., Paley graphs).
- The use of Fourier analysis to transform SDPs into LPs for structured graphs (circulant graphs).

Conclusion

"Randomstrasse101: Open Problems of 2025" is a vital resource for researchers in probability and combinatorics. It not only lists unsolved conjectures but contextualizes them within the latest theoretical frameworks (e.g., Matrix Chaoses, Stochastic Localization). The manuscript underscores that while significant progress has been made (e.g., in the KLS and Slicing problems), fundamental questions regarding the limits of convex relaxations, the geometry of high-dimensional spaces, and the existence of specific combinatorial structures (like MUBs and SIC-POVMs) remain active and challenging frontiers.