16 citations · 35 across the 16 of their papers we have counts for
19 papers
On the Complexity of Recurrence Evaluation
Artem Parfenov, Michael Vyalyi
In this paper, we study the complexity of the recurrence evaluation problem. We are interested in finitely valued recurrent functions. We present two results in this direction. Fir…
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems
Alexander Rubtsov, Mikhail Vyalyi
We consider general computational models: one-way and two-way finite automata, and logarithmic space Turing machines, all equipped with an auxiliary data structure (ADS). The defin…
Avoidability beyond paths
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
The concept of avoidable paths in graphs was introduced by Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius in 2019 as a common generalization of avoidable vertices and simpli…
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…
Shifting paths to avoidable ones
Vladimir Gurvich, Matjaž Krnc, Martin Milanič +1
An extension of an induced path in a graph is an induced path such that deleting the endpoints of results in . An induced path in a graph is said to be avoidab…
Re-pairing brackets
Dmitry Chistikov, Mikhail Vyalyi
Consider the following one-player game. Take a well-formed sequence of opening and closing brackets. As a move, the player can pair any opening bracket with any closing bracket to…