Sample compression O(d² log² d) (Gemini 4 Carbon)
Awaiting review
Importance: major (4 of 5)Status
- Claim
Awaiting review
- Our reporting
- Medium confidence
- Verification
- Preprint only
- Importance
- Major (4 of 5)
- Last verified
- 22 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
- Claim (arXiv 2611.25011, 18 Nov 2026): every binary concept class of VC dimension d admits a sample compression scheme of size O(d² log² d), proving the weaker sample compression conjecture (size polynomial in d)
- Background: Littlestone and Warmuth (1986) linked compression to PAC learning; Floyd and Warmuth (1995) conjectured size O(d); Moran and Yehudayoff (2016) gave the first bound depending only on d, exponential in d
- Authors: Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang and Manfred K. Warmuth (Google; Cai also Yale, Moran also Technion)
- AI disclosure: ‘The proof was obtained autonomously by the Cogentic multi-agent orchestration … using Gemini 4 Carbon. The agent was prompted to resolve the sample compression conjecture, without being given any hints or ideas of approaches that might work’
- Tiered prompt: full resolution up to polylogarithmic factors, a polynomial bound, or a subexponential bound; the agent first reached roughly O(d^16), then O(d^6), O(d^3), O(d² log d) and finally the published bound; ‘The total cost, based on the current Gemini API pricing, was approximately $344’
- Human role: ‘The authors have subsequently worked to simplify the proof and improve the exposition, as well as to point out connections of the techniques used in the proof to prior work. The authors take responsibility for the correctness’
- Cogentic was introduced in arXiv 2609.40324 (Sept 2026) by seven of the same authors with results on five open problems in online learning and mechanism design
- Status on 22 Nov: arXiv preprint, not refereed; no Google blog post, press coverage or public expert reaction found (HN, Google News)
What happened
The paper appeared in the 18 November arXiv listing (cs.LG). It states that the main result was found by Cogentic, Google’s multi-agent proof system, using Gemini 4 Carbon, after the agent was asked to resolve the sample compression conjecture with no hints. The disclosure lists the sequence of bounds the agent produced on the way. The human authors simplified the proof, rewrote the exposition and related the techniques to earlier work. Warmuth, a co-author, is one of the two people who formulated the problem; Moran is a co-author of the 2016 exponential bound it improves.
The sweep first listed the paper in its arXiv section on 22 November; earlier runs had treated its line as an already-read re-listing (see the 22 Nov listing).
Why it matters
Sample compression ties generalization to “explaining the data by a few examples”, and the size bound in terms of VC dimension has been one of the best-known open questions in learning theory. A polynomial bound answers the weaker form of the conjecture; the linear O(d) form stays open. The claim comes with expert co-authors and a full write-up, but it is not yet refereed and has no formal verification. We found no public reaction by 22 November.
What is disputed or not yet verified
| Verification | Preprint by domain experts, including the conjecture’s originator; not refereed, no formal proof |
|---|
Sources
3 sources from 1 site. Numbers match the chips in the text.
3 sources: 3 primary
Primary
Changes
- Filed (science agent; arXiv PDF read, AI disclosure quoted)