Mikhail N. Vyalyi

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 19

Top Topics

Top Venues

Probl. Inf. Transm.

Publications

Vladimir Gurvich, Matjaz Krnc, Mikhail N. Vyalyi
Growing Trees and Amoebas' Replications. CoRR (2024)
Endre Boros, Paolo Giulio Franciosa, Vladimir Gurvich, Mikhail N. Vyalyi
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies. Int. J. Game Theory 53 (2) (2024)
Mikhail N. Vyalyi
Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements. Probl. Inf. Transm. 59 (1) (2023)
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
Shifting paths to avoidable ones. J. Graph Theory 100 (1) (2022)
Alexander A. Rubtsov, Mikhail N. Vyalyi
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems. CoRR (2022)
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
Avoidability beyond paths. CoRR (2022)
Alexander A. Rubtsov, Mikhail N. Vyalyi
On computational complexity of set automata. Inf. Comput. 281 (2021)
Mikhail N. Vyalyi
Counting the Number of Perfect Matchings, and Generalized Decision Trees. Probl. Inf. Transm. 57 (2) (2021)
Alexander A. Rubtsov, Mikhail N. Vyalyi
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems. DCFS (2021)
Vladimir Gurvich, Mikhail N. Vyalyi
On Computational Hardness of Multidimensional Subtraction Games. Algorithms 14 (3) (2021)
Vladimir Gurvich, Mikhail N. Vyalyi
Computational Hardness of Multidimensional Subtraction Games. CSR (2020)
Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi
Shifting paths to avoidable ones. CoRR (2020)
Mikhail N. Vyalyi, V. K. Leontiev
Geometry of Translations on a Boolean Cube. Probl. Inf. Transm. 55 (2) (2019)
Alexander A. Rubtsov, Mikhail N. Vyalyi
On Emptiness and Membership Problems for Set Automata. CSR (2018)
Alexander A. Rubtsov, Mikhail N. Vyalyi
On computational complexity of Set Automata. CoRR (2017)
Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik
Grünbaum coloring and its generalization to arbitrary dimension. Australas. J Comb. 67 (2017)
Alexander A. Rubtsov, Mikhail N. Vyalyi
On Computational Complexity of Set Automata. DLT (2017)
Mikhail N. Vyalyi, I. M. Khuziev
Fast protocols for leader election and spanning tree construction in a distributed network. Probl. Inf. Transm. 53 (2) (2017)
Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik
Grünbaum coloring and its generalization to arbitrary dimension. CoRR (2016)
Alexander A. Rubtsov, Mikhail N. Vyalyi
Regular Realizability Problems and Context-Free Languages. DCFS (2015)
Mikhail N. Vyalyi, Alexander A. Rubtsov
On regular realizability problems for context-free languages. Probl. Inf. Transm. 51 (4) (2015)
Alexander A. Rubtsov, Mikhail N. Vyalyi
Regular realizability problems and context-free languages. CoRR (2015)
Mikhail N. Vyalyi, I. M. Khuziev
Distributed communication complexity of spanning tree construction. Probl. Inf. Transm. 51 (1) (2015)
Mikhail N. Vyalyi
Universality of Regular Realizability Problems. CSR (2013)
Mikhail N. Vyalyi
On expressive power of regular realizability problems. Probl. Inf. Transm. 49 (3) (2013)
Vladimir Gurvich, Mikhail N. Vyalyi
Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs. Discret. Appl. Math. 160 (12) (2012)
Mikhail N. Vyalyi
On complexity of regular realizability problems CoRR (2012)
Mikhail N. Vyalyi
On regular realizability problems. Probl. Inf. Transm. 47 (4) (2011)
Alexander A. Rubtsov, Mikhail N. Vyalyi
Regular realizability problems and models of a generalized nondeterminism CoRR (2011)
Sergey P. Tarasov, Mikhail N. Vyalyi
Orbits of Linear Maps and Regular Languages. CSR (2011)
Qi Cheng, Sergey P. Tarasov, Mikhail N. Vyalyi
Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing. Theory Comput. Syst. 46 (1) (2010)
R. A. Gimadeev, Mikhail N. Vyalyi
Identical Relations in Symmetric Groups and Separating Words with Reversible Automata. CSR (2010)
Sergey P. Tarasov, Mikhail N. Vyalyi
Orbits of linear maps and regular languages CoRR (2010)
Mikhail N. Vyalyi
On Models of a Nondeterministic Computation. CSR (2009)
Mikhail N. Vyalyi
On models of a nondeterministic computation CoRR (2008)
Sergey P. Tarasov, Mikhail N. Vyalyi
Semidefinite programming and arithmetic circuit evaluation. Discret. Appl. Math. 156 (11) (2008)
Sergey P. Tarasov, Mikhail N. Vyalyi
An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity. CSR (2007)
Sergey Bravyi, Mikhail N. Vyalyi
Commutative version of the local Hamiltonian problem and common eigenspace problem. Quantum Inf. Comput. 5 (3) (2005)
Sergey P. Tarasov, Mikhail N. Vyalyi
Semidefinite programming and arithmetic circuit evaluation CoRR (2005)
Mikhail N. Vyalyi
QMA=PP implies that PP contains PH Electron. Colloquium Comput. Complex. 10 (021) (2003)