Cover Image

Separating complexity classes of LCL problems on grids

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Berlow, Katalin, Bernshteyn, Anton, Lyons, Clark, Weilacher, Felix
Format:	Preprint
Published:	2025
Subjects:	Logic Computational Complexity Combinatorics Probability
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Borel versions of the Local Lemma and LOCAL algorithms for graphs of finite asymptotic separation index
by: Bernshteyn, Anton, et al.
Published: (2023)

Borel Local Lemma: arbitrary random variables and limited exponential growth
by: Bernshteyn, Anton, et al.
Published: (2024)

Embedding Borel graphs into grids of asymptotically optimal dimension
by: Bernshteyn, Anton, et al.
Published: (2024)

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies
by: Li, Yaqiao
Published: (2025)

Borel Polychromatic Number of Grids
by: Berlow, Katalin, et al.
Published: (2025)

Borel line graphs
by: Anderson, James, et al.
Published: (2023)

Borel Vizing's Theorem for Graphs of Subexponential Growth
by: Bernshteyn, Anton, et al.
Published: (2023)

First order complexity of finite random structures
by: Demin, Danila, et al.
Published: (2024)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
by: Feller, Roman, et al.
Published: (2024)

LCLs in the Borel Hierarchy
by: Weilacher, Felix
Published: (2026)

A very sharp threshold for first order logic distinguishability of random graphs
by: Benjamini, Itai, et al.
Published: (2022)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Permanents of random matrices over finite fields
by: Hunter, Zach, et al.
Published: (2026)

Optimal Union Probability Interval Is NP-Hard
by: Kaski, Petteri, et al.
Published: (2026)

Large-scale geometry of Borel graphs of polynomial growth
by: Bernshteyn, Anton, et al.
Published: (2023)

How to fit large complexity classes into TFNP
by: Thapen, Neil
Published: (2024)

Some easy optimization problems have the overlap-gap property
by: Li, Shuangping, et al.
Published: (2024)

Restricted CSPs and F-free Digraph Algorithmics
by: Guzmán-Pro, Santiago, et al.
Published: (2025)

The Richness of CSP Non-redundancy
by: Brakensiek, Joshua, et al.
Published: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
by: Kiefer, Sandra, et al.
Published: (2025)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
by: Seppelt, Tim
Published: (2023)

Borel Homomorphisms from Forests to Kneser Graphs
by: Weilacher, Felix
Published: (2026)

Finding hardness reductions automatically using SAT solvers
by: Bergold, Helena, et al.
Published: (2024)

Computable vs Descriptive Combinatorics of Local Problems on Trees
by: Weilacher, Felix
Published: (2022)

Infinite circle patterns in the Weil-Petersson class
by: Lam, Wai Yeung
Published: (2026)

Generic sampling and invariant measures on the space of $k$-uniform hypergraphs
by: Ackerman, Nathanael, et al.
Published: (2025)

A logical limit law for the sequential model of preferential attachment graphs
by: Özdemir, Alperen
Published: (2024)

Logical limit laws for Mallows random permutations
by: Muller, Tobias, et al.
Published: (2023)

A logical approach to concentration
by: Benedikt, Michael, et al.
Published: (2026)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Noise Sensitivity and Learning Lower Bounds for Hierarchical Functions
by: Li, Rupert, et al.
Published: (2025)

Proof complexity of Mal'tsev CSP
by: Gaysin, Azza
Published: (2025)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Decidability in geometric grid classes of permutations
by: Braunfeld, Samuel
Published: (2023)

Universality for roots of derivatives of entire functions via finite free probability
by: Campbell, Andrew, et al.
Published: (2024)

The ineffectiveness of the regularity lemma for bounded degree graphs
by: Lyons, Clark, et al.
Published: (2025)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
by: Roberson, David E., et al.
Published: (2023)

Polynomial-time sampling despite disorder chaos
by: Ma, Eric, et al.
Published: (2025)