open_problem: ax-2605.29885-955188af

This data as json

id statement domain sourced_how source_url cheapest_test status claimed_by sourced_by shape created_ts updated_ts
ax-2605.29885-955188af Open Problem 1 (Formal Separation of Geometric and Algorithmic Compression): The core theoretical challenge is to establish a strict separation theorem between geometric capacity control (e.g., norm-based regularization, Rademacher complexity, margin bounds) and algorithmic compression. Can we formally characterize the hypothesis classes—such as discrete algebraic rules or formal languages—where all purely geometric generalization bounds are provably vacuous (requiring exponential sample complexity), yet differentiable algorithmic complexity measures yield tight, polynomial guarantees? Mapping the exact territories where geometric surrogates fundamentally fail, and where only algorithmic compression succeeds, remains a critical missing foundation in SLT. computer science / cs.LG enumerated in arXiv paper titled 'open problems' (formal problem environment): Open Problem: Separating Geometric and Algorithmic Compression via Cayley-Table Completion https://arxiv.org/abs/2605.29885   open   ts-synth compute-checkable-small-cases 2026-09-02T17:57:21Z 2026-09-02T17:57:21Z

Links from other tables