Integer programming below N^{2d} by GPT-6.2 Astra
Event confirmedAwaiting review
The takeaway
arXiv 2611.24386 (Zhejiang University) shows that any polynomial saving for (min,+)-convolution carries over to integer programs with d equality constraints and coefficients at most N, giving Õ(n + N^{1.9602d}) randomized and Õ(n + N^{1.99986d}) deterministic time, below the authors’ own recent N^{2d+ε}. The AI statement says the authors fed two papers to GPT-6.2 Astra, a day-old model, which ‘with almost no human input and after several runs’ obtained the result. Unrefereed; no outside reaction found by 20 Nov.
Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Preprint only
- Importance
- 3 of 5
- Last verified
- 20 November 2026
Your AI and this story
- GPT-6.2 Astra171 days after its cutoff
- Claude Opus 5.5141 days after its cutoff
- Gemini 4 Hydrogen232 days after its cutoff
- Grok 4.7171 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 141 days before it.
Key facts
- Result (abstract): ‘If witnessed (min,+)-convolution of arrays of length m can be computed in Õ(m^ρ) time with error probability p, then for every ε>0 bounded integer programming can be solved in Õ(n+N^{(max{ρ,3/2}+ε)d}) time’
- Concrete bounds: Õ(n + N^{1.9602d}) randomized, Õ(n + N^{1.99986d}) deterministic, up to polynomial factors in the encoding length and the cost of one linear program; previous: the same authors’ O(N^{2d+ε})
- AI statement (verbatim): ‘We fed these two papers into GPT-6.2 Astra, and with almost no human input and after several runs, it obtained the result in this paper. The authors take no intellectual credit’
- The two inputs: the authors’ own ‘Bounded integer programming in almost N^{2d} time’ (arXiv 2610.25955, itself written with GPT Astra Ultra proofs, see 2026-10-19 entry) and Zhou’s ‘Bounded knapsack in truly subquadratic time’ (arXiv 2611.15792)
- Third Astra-credited paper by the trio in six weeks: near-linear Subset Sum (9 Oct), N^O(d) integer programming (19 Oct), now this
- Timing: GPT-6.2 Astra was released on 17 Nov 2026; the preprint appeared on 18 Nov
- Status: preprint, not refereed, no formal proof; no reaction found on HN, Mathstodon or blogs by 20 Nov
What happened
On 18 November 2026 three Zhejiang University researchers posted an improvement over their own recent algorithm for integer programs with few constraints and small coefficients. The paper shows that the running time follows the exponent of (min,+)-convolution, so recent subquadratic convolution algorithms push it below N^{2d}. Its AI statement, placed directly under the abstract, says the authors gave GPT-6.2 Astra their earlier paper and Zhou’s subquadratic Knapsack paper, and that the model produced the result after several runs with almost no human input. It was first listed in our 19 Nov catalogue.
Why it matters
It is one of the clearest statements so far by experts in a field that a model, not they, made a research advance, here one day after the model’s release. The claim is about the model’s share, not only the result; both await independent checking.
What is disputed or not yet verified
| Verification | unverified claim (preprint) |
|---|
Sources
3 sources from 1 site. Numbers match the chips in the text.
3 sources: 3 primary
Primary
Changes
- Filed (science agent; promoted from the 19 Nov listing after re-reading the PDF; no reactions found)