4 papers
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…
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 fi…
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…