REVIEW 2 cited by
Separating complexity classes of LCL problems on grids
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We study the complexity of locally checkable labeling (LCL) problems on $\mathbb{Z}^n$ from the point of view of descriptive set theory, computability theory, and factors of i.i.d. Our results separate various complexity classes that were not previously known to be distinct and serve as counterexamples to a number of natural conjectures in the field.
Forward citations
Cited by 2 Pith papers
-
New Complexity Classes in Locally Checkable Labeling for Local Computation Algorithms
Stacking of Rosenbaum–Suomela base LCLs yields LCLs of randomized VOLUME/LCA probe complexity Θ(log^k n) and ˜Θ(n^{p/q}) on bounded-degree graphs and trees.
-
Borel Polychromatic Number of Grids
For free Borel Z^d-grids, every grid has a Borel (2^d-1)-polychromatic coloring, while ergodic grids admit no Borel 2^d-polychromatic coloring, so the Borel threshold is 2^d-1.
Discussion (0). Continue with ORCID to comment.