4 papers
Complexity of Finite Borel Asymptotic Dimension
Jan GrebÃk, Cecelia Higgins
We show that the set of locally finite Borel graphs with finite Borel asymptotic dimension is -complete. The result is based on a combinatorial characterization of f…
Deterministic Distributed Algorithms and Measurable Combinatorics on -Regular Forests
Sebastian Brandt, Yi-Jun Chang, Jan GrebÃk +3
We investigate the connections between the fields of distributed computing and measurable combinatorics by considering complexity classes of locally checkable labeling problems on…
From descriptive to distributed
Jan GrebÃk, Zoltán Vidnyánszky
In the past couple of years a rich connection has been found between the fields of descriptive set theory and distributed computing. Frequently, and less surprisingly, finitary alg…
Complexity of Linear Equations and Infinite Gadgets
Jan GrebÃk, Zoltán Vidnyánszky
We investigate the descriptive set-theoretic complexity of the solvability of a Borel family of linear equations over a finite field. Answering a question of Thornton, we show that…