2 papers
math.CO2025
The ineffectiveness of the regularity lemma for bounded degree graphs
Clark Lyons, Grigory Terlov, Zoltán Vidnyánszky
We show that for any , there is no bound computable from on the size of a graph required to approximate a graph of maximum degree at most up to $\…
math.LO2025
Separating complexity classes of LCL problems on grids
Katalin Berlow, Anton Bernshteyn, Clark Lyons +1
We study the complexity of locally checkable labeling (LCL) problems on from the point of view of descriptive set theory, computability theory, and factors of i.i.d.…