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.

Original post →

More from Research

Research channel →