New paper proves weak sample compression conjecture with O(d² log² d) scheme
canondetortugas · x · 2026-11-21
A new arXiv paper, 'Near-Quadratic Sample Compression for All VC Classes' by Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Shay Moran, Grigoris Velegkas, Di Wang, and Manfred K. Warmuth, resolves the weak version of the longstanding sample compression conjecture. The Floyd–Warmuth conjecture (1995) asked whether every VC class admits a compression scheme of size polynomial in d; the previous best bound depending only on d was exponential (Moran–Yehudayoff 2016). The authors construct a scheme of size O(d² log² d), a major advance in learning theory.
More from Research
- Lean Community Verifies 17M Lines of Code, Confirms Claude-Assisted Riemann Hypothesis Proof — Polymarket · 2026-11-22
- Kotoba CEO: Audio Tokenization Is the Core Research Problem in Real-Time Speech AI — lmthang · 2026-11-22
- Optogenetics could have been invented in the 1970s — how common are biology's 'delayed inventions'? — NikoMcCarty · 2026-11-22
- Gordic: interpretability of looped transformers likely no harder than deep models — gordic_aleksa · 2026-11-22
- NeurIPS 2026 Paper π-Fold Uses Physics-Informed RL to Fix Atom-Level Errors in Folding Models — lmthang · 2026-11-22
- Soon the interesting bit in math is minimizing Kolmogorov complexity of proofs — gordic_aleksa · 2026-11-22