3 papers
cs.GT2022
State Complexity of Chromatic Memory in Infinite-Duration Games
Alexander Kozachinskiy
A major open problem in the area of infinite-duration games is to characterize winning conditions that are determined in finite-memory strategies. Infinite-duration games are usual…
math.CO2021
Uniform cross--intersecting families: proving Hirschorn's conjecture up to polynomial factor
Georgii P. Bulgakov, Alexander Kozachinskiy, Mikhail N. Vyalyi
We consider a problem of maximizing the product of the sizes of two uniform cross--intersecting families of sets. We show that the value of this maximum is at most polynomially…
cs.FL2019
An application of communication complexity, Kolmogorov complexity and extremal combinatorics to parity games
Alexander Kozachinskiy, Mikhail Vyalyi
So-called separation automata are in the core of several recently invented quasi-polynomial time algorithms for parity games. An explicit -state separation automaton implies an…