Mikhail N. Vyalyi

50 papers A* 1C 1Misc 7Journal 37Unranked 3
YearRankTypeTitle / Venue / Authors
2025 J jnl
Avoidability Beyond Paths.
Electron. J. Comb.
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
2025 — conf
Disjunctive Complexity.
DCFS
Nikita Ivanov, Alexander A. Rubtsov, Mikhail N. Vyalyi
2025 J jnl
Disjunctive Complexity.
CoRR
Nikita Ivanov, Alexander A. Rubtsov, Mikhail N. Vyalyi
2024 J jnl
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies.
Int. J. Game Theory
Endre Boros, Paolo Giulio Franciosa, Vladimir Gurvich, Mikhail N. Vyalyi
2024 J jnl
Growing Trees and Amoebas' Replications.
CoRR
Vladimir Gurvich, Matjaz Krnc, Mikhail N. Vyalyi
2024 J jnl
On Universality of Regular Realizability Problems.
Probl. Inf. Transm.
Alexander A. Rubtsov, Mikhail N. Vyalyi
2024 J jnl
Two-person positive shortest path games have Nash equlibria in pure stationary strategies.
CoRR
Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Mikhail N. Vyalyi
2023 J jnl
Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements.
Probl. Inf. Transm.
Mikhail N. Vyalyi
2022 J jnl
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems.
CoRR
Alexander A. Rubtsov, Mikhail N. Vyalyi
2022 J jnl
Avoidability beyond paths.
CoRR
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
2022 J jnl
Shifting paths to avoidable ones.
J. Graph Theory
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
2021 — conf
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems.
DCFS
Alexander A. Rubtsov, Mikhail N. Vyalyi
2021 J jnl
Counting the Number of Perfect Matchings, and Generalized Decision Trees.
Probl. Inf. Transm.
Mikhail N. Vyalyi
2021 J jnl
On Computational Hardness of Multidimensional Subtraction Games.
Algorithms
Vladimir Gurvich, Mikhail N. Vyalyi
2021 J jnl
On computational complexity of set automata.
Inf. Comput.
Alexander A. Rubtsov, Mikhail N. Vyalyi
2020 Misc conf
Computational Hardness of Multidimensional Subtraction Games.
CSR
Vladimir Gurvich, Mikhail N. Vyalyi
2020 A* conf
Re-pairing brackets.
LICS
Dmitry Chistikov, Mikhail N. Vyalyi
2020 J jnl
Shifting paths to avoidable ones.
CoRR
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
2019 J jnl
Geometry of Translations on a Boolean Cube.
Probl. Inf. Transm.
Mikhail N. Vyalyi, V. K. Leontiev
2019 J jnl
Lower bounds on separation automata for Parity Games.
CoRR
Alexander Kozachinskiy, Mikhail N. Vyalyi
2019 J jnl
Re-pairing brackets.
CoRR
Dmitry Chistikov, Mikhail N. Vyalyi
2018 Misc conf
On Emptiness and Membership Problems for Set Automata.
CSR
Alexander A. Rubtsov, Mikhail N. Vyalyi
2017 J jnl
Exploring the bounds on the positive semidefinite rank.
CoRR
Andrii Riazanov, Mikhail N. Vyalyi
2017 J jnl
Fast protocols for leader election and spanning tree construction in a distributed network.
Probl. Inf. Transm.
Mikhail N. Vyalyi, I. M. Khuziev
2017 J jnl
Grünbaum coloring and its generalization to arbitrary dimension.
Australas. J Comb.
Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik
2017 C conf
On Computational Complexity of Set Automata.
DLT
Alexander A. Rubtsov, Mikhail N. Vyalyi
2017 J jnl
On computational complexity of Set Automata.
CoRR
Alexander A. Rubtsov, Mikhail N. Vyalyi
2016 J jnl
Grünbaum coloring and its generalization to arbitrary dimension.
CoRR
Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik
2015 J jnl
Distributed communication complexity of spanning tree construction.
Probl. Inf. Transm.
Mikhail N. Vyalyi, I. M. Khuziev
2015 J jnl
On regular realizability problems for context-free languages.
Probl. Inf. Transm.
Mikhail N. Vyalyi, Alexander A. Rubtsov
2015 — conf
Regular Realizability Problems and Context-Free Languages.
DCFS
Alexander A. Rubtsov, Mikhail N. Vyalyi
2015 J jnl
Regular realizability problems and context-free languages.
CoRR
Alexander A. Rubtsov, Mikhail N. Vyalyi
2013 J jnl
On expressive power of regular realizability problems.
Probl. Inf. Transm.
Mikhail N. Vyalyi
2013 Misc conf
Universality of Regular Realizability Problems.
CSR
Mikhail N. Vyalyi
2012 J jnl
Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs.
Discret. Appl. Math.
Vladimir Gurvich, Mikhail N. Vyalyi
2012 J jnl
On complexity of regular realizability problems
CoRR
Mikhail N. Vyalyi
2011 J jnl
On regular realizability problems.
Probl. Inf. Transm.
Mikhail N. Vyalyi
2011 Misc conf
Orbits of Linear Maps and Regular Languages.
CSR
Sergey P. Tarasov, Mikhail N. Vyalyi
2011 J jnl
Regular realizability problems and models of a generalized nondeterminism
CoRR
Alexander A. Rubtsov, Mikhail N. Vyalyi
2010 J jnl
Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing.
Theory Comput. Syst.
Qi Cheng, Sergey P. Tarasov, Mikhail N. Vyalyi
2010 Misc conf
Identical Relations in Symmetric Groups and Separating Words with Reversible Automata.
CSR
R. A. Gimadeev, Mikhail N. Vyalyi
2010 J jnl
Orbits of linear maps and regular languages
CoRR
Sergey P. Tarasov, Mikhail N. Vyalyi
2009 Misc conf
On Models of a Nondeterministic Computation.
CSR
Mikhail N. Vyalyi
2008 J jnl
On models of a nondeterministic computation
CoRR
Mikhail N. Vyalyi
2008 J jnl
Semidefinite programming and arithmetic circuit evaluation.
Discret. Appl. Math.
Sergey P. Tarasov, Mikhail N. Vyalyi
2007 Misc conf
An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity.
CSR
Sergey P. Tarasov, Mikhail N. Vyalyi
2005 J jnl
Commutative version of the local Hamiltonian problem and common eigenspace problem.
Quantum Inf. Comput.
Sergey Bravyi, Mikhail N. Vyalyi
2005 J jnl
Semidefinite programming and arithmetic circuit evaluation
CoRR
Sergey P. Tarasov, Mikhail N. Vyalyi
2003 J jnl
QMA=PP implies that PP contains PH
Electron. Colloquium Comput. Complex.
Mikhail N. Vyalyi
2002 — book
Classical and Quantum Computation.
Alexei Y. Kitaev, A. H. Shen, Mikhail N. Vyalyi