Berkeley’s Phillip Kerger uses GPT-5.6 Sol and a 10-page prompt to close a 30-year gap in derivative-free convex optimization
Awaiting review
The takeaway
In July 2026 UC Berkeley IEOR teaching professor Phillip Kerger posted a proof that deterministic optimization of a convex Lipschitz function over a d-dimensional ball with only exact function values needs Ω(d²/log(d+1)) queries.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 19 October 2026
Your AI and this story
- GPT-6.2 Astra44 days after its cutoff
- Claude Opus 5.514 days after its cutoff
- Gemini 4 Hydrogen105 days after its cutoff
- Grok 4.744 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 14 days before it.
Key facts
- Paper: arXiv 2607.13335, ‘Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimization: A Near-Quadratic Lower Bound from Exact Function Values’ (Phillip Kerger, submitted July 14, 2026, 36 pages); it also gives Õ(d²·2ⁿ) results for mixed-integer problems
- Result: Ω(d²/log(d+1)) deterministic exact-value query lower bound vs O(d² log² d) upper bound from Protasov’s 1996 method; the previously applicable lower bound was Ω(d)
- AI role (Kerger’s Medium post, as reported by temperature2 and AI Weekly): a ~10-page prompt with background, techniques and direction; the model produced a complete proof in ~2.5 hours without intervention. Kerger had worked on the gap for about a year. AI Weekly names the model ‘GPT-5.6 Sol Pro’
- Lean 4/mathlib companion repo (PhillipKerger/zero-order-bounds-lean-verification, created July 14) fully verifies the paper’s deterministic d^(-1/2)-accuracy lower bound, including Brunn–Minkowski and Urysohn machinery; the upper-bound and transfer results are outside the formalization
- The arXiv abstract itself does not mention AI. The AI-assistance claim rests on the author’s own blog post
- Attention: r/math post ‘After OpenAI’s CDC proof announcement, GPT-5.6 used a prompt to close a 30-year gap in convex optimization’ reached the Hacker News front page (601 points, July 18)
- Follow-up: Zhang, Zhang, Qi and Lin (arXiv 2607.16558, July 18) proved near-optimal lower bounds for randomized algorithms in the same exact-value setting (no AI mentioned)
What happened
A few days after OpenAI’s cycle double cover proof, Kerger applied the same kind of long, structured prompt to a problem he had worked on for a year. The question is how many function evaluations a deterministic method needs to minimize a convex function when it sees only exact values and no gradients. Protasov’s 1996 method needs about d² evaluations, but the best lower bound was only about d. The model’s argument establishes a near-quadratic lower bound. Kerger then had the core result machine-checked in Lean and published the paper, the Lean code and (reportedly) the prompt and chat logs.
Why it matters
Most of the summer’s AI-math headlines came from the labs themselves. This was an outside, single-author result with a formal proof, on a well-defined classical gap, and it suggested the recipe transfers to other areas of mathematics. Caveat: the Medium post with the step-by-step AI account could not be read directly here, because of a Cloudflare block. Details of the AI’s role come from secondary summaries of it.
What is disputed or not yet verified
| Verification | Partial Lean: the core deterministic lower bound is formally verified in Lean 4 (public repo); the upper-bound and transfer results are not formalized; unrefereed single-author preprint |
|---|
Sources
7 sources from 6 sites. Numbers match the chips in the text.
7 sources: 4 primary, 2 press, 1 reaction
Primary
- arXiv 2607.13335: Closing the Oracle-Complexity Gap in Derivative-Free Convex Optimizationarxiv.org, paper
- GitHub: PhillipKerger/zero-order-bounds-lean-verification (Lean 4 companion)github.com, code
- Phillip Kerger (Medium): An AI-assisted breakthrough in convex optimizationmedium.com, official
- arXiv 2607.16558: Near-optimal lower bounds for randomized algorithms (follow-up)arxiv.org, paper
Press
- temperature2: GPT-5.6 closes a second 30-year math gap without OpenAItemperature2.com, press
- AI Weekly: GPT-5.6 Sol Pro closes 30-year gap in zeroth-order convex optimization, Lean-verifiedaiweekly.co, press
Reactions
- Hacker News discussion (601 points)news.ycombinator.com, discussion
Changes
- Status confirmed → pending (only part of the paper is Lean-verified; the preprint is unrefereed)
- Filed (r/math / HN item)