Integer programming in standard form in N^O(d) time, improving Eisenbrand–Weismantel’s N^O(d²): Zhejiang team’s ideas, GPT Astra Ultra’s proofs (Chen, Mao, Zhang)
Awaiting review
Importance: major (4 of 5)The takeaway
Ten days after their Subset Sum claim, the same Zhejiang trio claim to settle a basic question in integer programming. With d constraints and entries bounded by N, the running time exponent drops from O(d²) to linear in d. As before, the authors give the idea and say GPT Astra Ultra wrote the complete proofs.
Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Lean-verified
- Importance
- Major (4 of 5)
- Last verified
- 20 October 2026
Your AI and this story
- GPT-6 Astra172 days after its cutoff
- Claude Opus 5.5111 days after its cutoff
- Gemini 4 Argon202 days after its cutoff
- Grok 4.7141 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 111 days before it.
Key facts
- Paper: arXiv 2610.25955 [cs.DS], 19 Oct 2026, Lin Chen, Yuchen Mao, Guochuan Zhang (Zhejiang University). Builds on their 9 Oct Subset Sum / IP feasibility paper (arXiv 2610.12953)
- Result: deterministic poly(L_in) + f(d) N^O(d) (1 + log(c_max + 1))^O(1) time for standard-form integer programs with d equality constraints and bounded variables; ‘Prior to our work, the best known running time was N^O(d²) [Eisenbrand & Weismantel’20] … We answer this question affirmatively’
- Technique (contents): feasibility background ‘interior is easy, boundary reduces’; LP pricing to ‘separate the unavoidable cost from the repair’; an affordable interior/boundary test with a boundary branch (‘few large changes, then a smaller problem’) and an interior branch
- AI statement, verbatim: ‘The main proof route was designed by the authors, building upon their recent work on subset sum and integer programming feasibility [11]. The authors came up with the basic idea of adapting the algorithmic technique for integer programming feasibility test to optimization, and GPT Astra Ultra was used to turn the insights of the authors into complete mathematical proofs. GPT and Claude were used for drafting the paper. GPT also verified this papers main results using the Lean 4 proof.’
- Caveats: no Lean repository is linked in the PDF; no independent check or expert reaction found by 20 Oct morning; the companion Subset Sum claim is also unreviewed
What happened
Eisenbrand and Weismantel’s 2020 proximity bound gave integer programs with few constraints an N^O(d²) algorithm. Chen, Mao and Zhang carry over the “interior is easy, boundary reduces” approach from their Subset Sum feasibility paper to optimization, and get an exponent linear in d. The division of labour matches their earlier paper: the authors supplied the plan, the model wrote the proofs.
Why it matters
If it holds, the result changes the best known running time for a core problem of combinatorial optimization. It is also the second claim in ten days in which one group says a GPT model turned its sketches into complete proofs of a long-standing algorithms question. That puts the weight on independent checking.
What is disputed or not yet verified
| Verification | Unrefereed arXiv preprint; authors report a GPT-made Lean 4 proof that is not linked |
|---|
Sources
2 sources from 1 site. Numbers match the chips in the text.
2 sources: 2 primary
Primary
Changes
- Filed (PDF read in full text)