ICM 2026 - IMU Abacus Medal Lecture - Shayan Oveis Gharan

ICM 2026 - IMU Abacus Medal Lecture - Shayan Oveis Gharan

by Shayan Oveis Gharan

Formal & Physical Sciences Mathematics PBMathematicsPBUOptimization
🎙 Shayan Oveis Gharan 👥 59K 📅 August 25, 2026 ⏱ 54 min 👁 5 📄 lecture 🧭 2026-08-25
Available in: English (current) Français

Keywords

real stablegenerating polynomialspanning treesTSPapproximation

Summary

Shayan Oveis Gharan, winner of the IMU Abacus Medal, delivers a lecture on the polynomial paradigm and its applications. He begins with the historical context of real-rooted polynomials and Pólya’s theorem, then introduces real stable polynomials as a multivariate generalization. He explains the concept of generating polynomials for probability distributions, using the uniform spanning tree distribution as a running example. He discusses the closure properties of real stable polynomials under operations like differentiation and substitution, and highlights the role of determinant polynomials as a starting point. He then presents applications in probability, showing how real stable polynomials lead to strongly Rayleigh distributions and enable results like a 43% lower bound on the probability of a vertex having even degree in a uniform spanning tree. He also covers a theorem on the existence of strongly Rayleigh distributions with prescribed means. The second major application is in approximation algorithms, specifically for the metric Traveling Salesperson Problem (TSP). He explains the classic Christofides algorithm and its 1.5 approximation ratio, then describes his work with collaborators improving this to a factor slightly better than 1.5. The key idea is to use a linear programming relaxation of TSP and sample a spanning tree from a carefully constructed strongly Rayleigh distribution with mean equal to the fractional solution, then add a matching. He outlines the analysis, showing that the expected cost of the tree is at most OPT and that the expected cost of the matching is less than half of OPT, using the degree distribution properties of the sampled tree.

255 words

Critical Evaluation

Value of the Information & Strength of the Argument

The lecture provides valuable insights into a powerful mathematical framework. The argumentation is solid, building from foundational definitions to advanced applications. The speaker clearly explains the logic behind each step, making the connections between polynomial properties and algorithmic results apparent. The presentation of the TSP algorithm is particularly compelling, showing how a theoretical concept (strongly Rayleigh distributions) directly leads to an improved approximation algorithm. The speaker also honestly acknowledges the limitations of current results, such as the gap between the proven bound and the conjectured performance.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, presenting results that have been published in top venues. The speaker cites the original authors of key theorems (Pólya, Schur, Borcea, Brändén, etc.) and his own collaborations. The title accurately reflects the content, as it is a lecture by the Abacus Medal winner. The description does not contain any links to sources, but the talk itself is a primary source for the research presented.

170 words

Title / Content Match

The title accurately reflects the content: a lecture by the Abacus Medal winner at ICM 2026, presenting his research on the polynomial paradigm.

Quality & Reliability

8/10

Lecture by a leading researcher (Abacus Medal winner) presenting original research and established results in mathematics and theoretical computer science. The content is rigorous, based on peer-reviewed work, and presented by the author himself. However, the talk is a high-level overview without full proofs, and some technical details are simplified.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

  • Pólya's theorem on real-rooted polynomials — Mentioned as the first theorem in the field of geometry of polynomials.
  • Borcea and Brändén's generalization of Pólya's theorem — Cited for the characterization of linear operators preserving real stability.
  • Christofides algorithm for TSP — Cited as the classic 1.5-approximation algorithm for metric TSP.
  • Dantzig, Fulkerson, and Johnson's LP relaxation for TSP — Mentioned as the origin of the linear programming relaxation used in the talk.

Concurring Sources

  • Borcea and Brändén, 'Multivariate Pólya-Schur theory' — The speaker's presentation aligns with the known results in this theory.

Contribution & Novelties

The lecture presents the speaker’s original contributions to the polynomial paradigm, including the improved approximation algorithm for TSP and the theorem on strongly Rayleigh distributions with prescribed means. It showcases how a deep understanding of real stable polynomials can lead to breakthroughs in algorithm design.

Pour aller plus loin :

79 words

Radar Profile

The radar profile shows high scores in information quality, technical level, and reliability, reflecting the depth and rigor of the lecture. The quantity of information is also high, though the lecture is a survey rather than a full technical exposition. The overall profile indicates a highly valuable and trustworthy source.

Reliability 9/10