Unfamiliar Terrain

Unfamiliar Terrain

by Prabhakar Raghavan

Formal & Physical Sciences AI — Models & Research UYQArtificial intelligence (AI)UYQFGenerative artificial intelligence
🎙 Prabhakar Raghavan 👥 75K 📅 May 28, 2026 ⏱ 29 min 👁 1K 📄 expert opinion 🧭 2026-08-03
Available in: English (current) Français

Keywords

AItheorem provingAlphaEvolvegadgetsverification

Summary

Prabhakar Raghavan, a senior figure at Google, presents a talk at the Simons Institute on the role of theoretical computer science (TCS) in modern machine learning, focusing on his experience using AlphaEvolve, a code mutation agent from Google DeepMind, to prove theorems. He begins with a puzzle about navigating a warehouse without a map, drawing a metaphor for unfamiliar terrain. He then discusses recent AI-assisted results in theorem proving, including OpenAI’s announcement on the unit distance problem. Raghavan explains AlphaEvolve’s workflow: an LLM generates programs that produce objects (e.g., graphs) which are scored and evolved. He presents several results: improved NP-hardness of approximation for TSP (ratio 111/110), improved max-4-cut gadget, results on max cut and independent set on random regular graphs, and new Ramanujan graphs. He emphasizes the importance of verification, using fast but potentially inaccurate verifiers for inner loops and exhaustive verification for final claims. He notes that gadgets are often small but asymmetric, and that mechanical gadget generation has precedents (Trevisan et al.). He concludes with reflections on what AI can and cannot do, suggesting that AI helps in finding small combinatorial objects but not in conceptual breakthroughs.

190 words

Critical Evaluation

The talk provides a valuable insider perspective on the practical use of AI in theoretical computer science. Raghavan is transparent about the limitations and the need for verification. He distinguishes between AI-generated gadgets and human-driven proof refactoring. The results, while incremental, are significant and have been verified. The discussion of fast verifiers is particularly interesting, as it highlights a pragmatic approach to search. However, the talk is not a formal presentation of results; it is more of a narrative. Some claims, such as OpenAI’s result, are taken at face value without independent verification. The speaker does not delve into the theoretical foundations of why AlphaEvolve works, which might be a missed opportunity. The audience interaction shows engagement and critical questioning, which adds to the credibility. Overall, the talk is informative and honest, but it is not a rigorous scientific paper. The title ‘Unfamiliar Terrain’ is apt, as the speaker is exploring new methods. The talk would benefit from more details on the specific problems and the nature of the AI’s contribution. The speaker’s emphasis on the obscurity of problems in some AI-assisted proofs is a candid admission. The talk is aimed at a specialized audience, but the core ideas are accessible. The lack of a formal structure and the reliance on anecdotal evidence are minor weaknesses. The talk does not provide a comprehensive review of the field, but it offers a unique case study. The speaker’s credibility and the concrete examples make it a valuable resource for those interested in AI for mathematics.

253 words

Title / Content Match

The title 'Unfamiliar Terrain' metaphorically captures the speaker's journey into using AI for theorem proving, which is the core of the talk.

Quality & Reliability

8/10

Talk by a senior industry researcher (Google) presenting recent results in theoretical computer science obtained with AI assistance. The speaker is credible and the results are presented with caveats about verification. However, the talk is not peer-reviewed and some claims (e.g., OpenAI's result) are taken from announcements.

Key Moments

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

Cited Sources

Concurring Sources

Contribution & Novelties

The talk provides a candid account of using AlphaEvolve for theorem proving, highlighting the importance of verification and the potential of AI to generate small combinatorial objects. It offers a practical perspective on the integration of AI into TCS research.

Pour aller plus loin :

  • AlphaEvolve (DeepMind) — Official blog post about AlphaEvolve.
  • Trevisan et al. on gadget generation — Reference to the paper on mechanical gadget generation.
  • OpenAI’s unit distance problem announcement — Official announcement of the result mentioned in the talk.

83 words

Radar Profile

The radar profile shows high scores in quantity, quality, and technical level, with a slightly lower but still high score in reliability. This indicates a technically dense and informative talk, with minor caveats regarding verification and reliance on announcements.

Reliability 8/10