1 citations · 1 across the 9 of their papers we have counts for
9 papers
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 $\va…
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…
Hyperfiniteness on Topological Ramsey Spaces
Balázs Bursics, Zoltán Vidnyánszky
We investigate the behavior of countable Borel equivalence relations (CBERs) on topological Ramsey spaces. First, we give a simple proof of the fact that every CBER on $[\mathbb{N}…
The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
Tamás Kátay, László Márton Tóth, Zoltán Vidnyánszky
We study Constraint Satisfaction Problems (CSPs) in an infinite context. We show that the dichotomy between easy and hard problems -- established already in the finite case -- pres…
Ramsey, expanders, and Borel chromatic numbers
Jan Grebík, Zoltán Vidnyánszky
We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.
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…
Ramsey and Hypersmoothness
Zoltán Vidnyánszky
Combining canonization results of Prömel-Voigt, Mathias, and Soare, we provide a new, natural example of an equivalence relation that is not hypersmooth.
On the existence of large antichains for definable quasi-orders
Benjamin D. Miller, Zoltán Vidnyánszky
We generalize Harrington-Marker-Shelah's Dilworth-style characterization of the existence of non-empty perfect antichains to co-analytic quasi-orders, establish the analogous theor…