1 citations · 2 across the 7 of their papers we have counts for
8 papers
Maximal Kolmogorov Complexity in a Hamming Ball
Alexander Kozachinskiy, Nikolay Vereshchagin
The minimal Kolmogorov complexity of a string within Hamming distance r of a given string x is the algorithmic rate-distortion function of x, and Vereshchagin and Vitanyi character…
Inapproximability of sufficient reasons for decision trees
Alexander Kozachinskiy
In this note, we establish the hardness of approximation of the problem of computing the minimal size of a -sufficient reason for decision trees.
Energy Games over Totally Ordered Groups
Alexander Kozachinskiy
Kopczyński (ICALP 2006) conjectured that prefix-independent half-positional winning conditions are closed under finite unions. We refute this conjecture over finite arenas. For tha…
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…
One-to-Two-Player Lifting for Mildly Growing Memory
Alexander Kozachinskiy
We investigate a phenomenon of "one-to-two-player lifting" in infinite-duration two-player games on graphs with zero-sum objectives. More specifically, let be a class of strate…
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…
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…
Some Bounds on Communication Complexity of Gap Hamming Distance
Alexander Kozachinskiy
In this paper we obtain some bounds on communication complexity of Gap Hamming Distance problem (): Alice and Bob are given binary string of length and t…