Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds

Abstract

In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph G of Littlestone dimension Lit(G)≤ℓ has a regular equipartition into excellent sets with (1 + o_{ε→ 0,ℓ}(1))·ε^−ℓ−1 parts and in the other direction, for every ℓ∈ℕ₊, there is an infinite family of graphs, all of Littlestone dimension ℓ, whose equipartitions into good sets must have size at least (1 + o_{ε→ 0,ℓ}(1))·ε^−ℓ−1. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative log(1/ε): every graph G with Lit(G)≤ℓ has a regular partition into excellent sets with (1 + o_{ε→ 0,ℓ}(1))·ε^−ℓ·ln(1/ε) parts and in the other direction, for every ℓ∈ℕ₊, there is an infinite family of graphs, all of Littlestone dimension ℓ, whose partitions into good sets must have size at least (1 + o_{ε→ 0,ℓ}(1))·ε^−ℓ. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the o_{ε→ 0,ℓ}(1) term above by a constant c > 0, we obtain randomized O_c,ε,ℓ(n·log(n))-time algorithms for partitions/equipartitions into good sets, a deterministic O_c,ε,ℓ(n²)-time algorithm for partitions into good sets, a deterministic O_c,ε,ℓ(n⁶)-time algorithm for equipartitions into good sets, a deterministic O_c,ℓ,ε(1)· n^{O(ℓ· 2^2·ℓ+4)}-time algorithm for partitions/equipartitions into excellent sets, and O_c,ε,ℓ(log(n+1))-space algorithms for partitions/equipartitions into good/excellent sets.

Partial Regularity of Stable Stationary Harmonic Maps into Compact Lie Groups
Jacob Krantz
arXiv28 Sep 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
A second-order energy-stable low-regularity integrator for the Navier--Stokes equations
Shu Ma
arXiv4 Oct 2026PreprintarXiv licenceFull textNumerical analysis & scientific computingarXiv
Existence and Regularity of Stable Resonant Spectral Submanifolds and Linearization Maps
Florian Kogelbauer, Rafael de la Llave
arXiv29 Oct 2026PreprintCC BY 4.0Full textDynamical systemsarXiv
Regularity of Structurally Stable Cusp Singularities for Two Families of Quasilinear Wave-type Equations
Samuel J. Armstrong, Geng Chen, Tao Huang +1
arXiv11 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Regularity of branched stable minimal immersed hypersurfaces
Gaoming Wang, Xuwen Zhang
arXiv1 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Geometry & topologyarXiv

Cite

BibTeX RIS

BibTeX

@misc{coregliano2026stable,
  title = {{Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds}},
  author = {Leonardo N. Coregliano and Fernando G. Jeronimo},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.25127},
  eprint = {2609.25127},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.25127},
}

RIS

TY  - UNPB
TI  - Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds
AU  - Leonardo N. Coregliano
AU  - Fernando G. Jeronimo
PY  - 2026
DA  - 2026/09/20
PB  - arXiv
DO  - 10.48550/arxiv.2609.25127
UR  - https://arxiv.org/abs/2609.25127
AB  - In this paper, we determine the precise asymptotics of the number of parts of stable regularity equipartitions in terms of the Littlestone dimension: every graph G of Littlestone dimension Lit(G)≤ℓ has a regular equipartition into excellent sets with (1 + o_ε→ 0,ℓ(1))·ε^−ℓ−1 parts and in the other direction, for every ℓ∈ℕ_+, there is an infinite family of graphs, all of Littlestone dimension ℓ, whose equipartitions into good sets must have size at least (1 + o_ε→ 0,ℓ(1))·ε^−ℓ−1. Dropping the equitability condition, we determine the asymptotics of non-equitable partitions up to a multiplicative log(1/ε): every graph G with Lit(G)≤ℓ has a regular partition into excellent sets with (1 + o_ε→ 0,ℓ(1))·ε^−ℓ·ln(1/ε) parts and in the other direction, for every ℓ∈ℕ_+, there is an infinite family of graphs, all of Littlestone dimension ℓ, whose partitions into good sets must have size at least (1 + o_ε→ 0,ℓ(1))·ε^−ℓ. We also show that such partition can be obtained algorithmically efficiently in an approximation scheme fashion: replacing the o_ε→ 0,ℓ(1) term above by a constant c > 0, we obtain randomized O_c,ε,ℓ(n·log(n))-time algorithms for partitions/equipartitions into good sets, a deterministic O_c,ε,ℓ(n^2)-time algorithm for partitions into good sets, a deterministic O_c,ε,ℓ(n^6)-time algorithm for equipartitions into good sets, a deterministic O_c,ℓ,ε(1)· n^O(ℓ· 2^2·ℓ+4)-time algorithm for partitions/equipartitions into excellent sets, and O_c,ε,ℓ(log(n+1))-space algorithms for partitions/equipartitions into good/excellent sets.
ER  -

Abstract

Related

Cite