Some PL Functions on Surfaces are not Height Functions. - Sergey P. Tarasov; Michael N. Vyalyi (SCG, 1997)

Construction of Contour Trees in 3D in O(n log n) Steps. - Sergey P. Tarasov; Michael N. Vyalyi (SCG, 1998)

A comparison of Zeroes and Ones of a Boolean Polynomial - Michael N. Vyalyi (CoRR, 2001)

Classical and Quantum Computation. - Alexei Y. Kitaev; A. H. Shen; Mikhail N. Vyalyi (American Mathematical Society, 2002)

Hardness of approximating the weight enumerator of a binary linear code - Michael N. Vyalyi (CoRR, 2003)

QMA=PP implies that PP contains PH - Mikhail N. Vyalyi (Electron. Colloquium Comput. Complex., 2003)

Commutative version of the local Hamiltonian problem and common eigenspace problem. - Sergey Bravyi 001; Mikhail N. Vyalyi (Quantum Inf. Comput., 2005)

An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity. - Sergey P. Tarasov; Mikhail N. Vyalyi (CSR, 2007)

Semidefinite programming and arithmetic circuit evaluation. - Sergey P. Tarasov; Mikhail N. Vyalyi (Discret. Appl. Math., 2008)

On Models of a Nondeterministic Computation. - Mikhail N. Vyalyi (CSR, 2009)

Identical Relations in Symmetric Groups and Separating Words with Reversible Automata. - R. A. Gimadeev; Mikhail N. Vyalyi (CSR, 2010)

Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing. - Qi Cheng 001; Sergey P. Tarasov; Mikhail N. Vyalyi (Theory Comput. Syst., 2010)

Orbits of Linear Maps and Regular Languages. - Sergey P. Tarasov; Mikhail N. Vyalyi (CSR, 2011)

Regular realizability problems and models of a generalized nondeterminism - Alexander A. Rubtsov; Mikhail N. Vyalyi (CoRR, 2011)

On regular realizability problems. - Mikhail N. Vyalyi (Probl. Inf. Transm., 2011)

On complexity of regular realizability problems - Mikhail N. Vyalyi (CoRR, 2012)

Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs. - Vladimir Gurvich; Mikhail N. Vyalyi (Discret. Appl. Math., 2012)

Universality of Regular Realizability Problems. - Mikhail N. Vyalyi (CSR, 2013)

On expressive power of regular realizability problems. - Mikhail N. Vyalyi (Probl. Inf. Transm., 2013)

Regular Realizability Problems and Context-Free Languages. - Alexander A. Rubtsov; Mikhail N. Vyalyi (DCFS, 2015)

Distributed protocols for spanning tree construction and leader election. - I. M. Khuziev; Michael N. Vyalyi (CoRR, 2015)

Distributed communication complexity of spanning tree construction. - Mikhail N. Vyalyi; I. M. Khuziev (Probl. Inf. Transm., 2015)

On regular realizability problems for context-free languages. - Mikhail N. Vyalyi; Alexander A. Rubtsov (Probl. Inf. Transm., 2015)

Grünbaum coloring and its generalization to arbitrary dimension. - Serge Lawrencenko; Mikhail N. Vyalyi; L. V. Zgonnik (Australas. J Comb., 2017)

Exploring the bounds on the positive semidefinite rank. - Andrii Riazanov; Mikhail N. Vyalyi (CoRR, 2017)

Fast protocols for leader election and spanning tree construction in a distributed network. - Mikhail N. Vyalyi; I. M. Khuziev (Probl. Inf. Transm., 2017)

On Emptiness and Membership Problems for Set Automata. - Alexander A. Rubtsov; Mikhail N. Vyalyi (CSR, 2018)

Lower bounds on separation automata for Parity Games. - Alexander Kozachinskiy; Mikhail N. Vyalyi (CoRR, 2019)

Geometry of Translations on a Boolean Cube. - Mikhail N. Vyalyi; V. K. Leontiev (Probl. Inf. Transm., 2019)

Re-pairing brackets. - Dmitry Chistikov 001; Mikhail N. Vyalyi (LICS, 2020)

Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems. - Alexander A. Rubtsov; Mikhail N. Vyalyi (DCFS, 2021)

On Computational Hardness of Multidimensional Subtraction Games. - Vladimir Gurvich; Mikhail N. Vyalyi (Algorithms, 2021)

On computational complexity of set automata. - Alexander A. Rubtsov; Mikhail N. Vyalyi (Inf. Comput., 2021)

Counting the Number of Perfect Matchings, and Generalized Decision Trees. - Mikhail N. Vyalyi (Probl. Inf. Transm., 2021)

Shifting paths to avoidable ones. - Vladimir Gurvich; Matjaz Krnc; Martin Milanic; Mikhail N. Vyalyi (J. Graph Theory, 2022)

Computer-assisted verification of confining two-rooted graphs with certain cages. - Vladimir Gurvich; Matjaz Krnc; Martin Milanic; Mikhail N. Vyalyi (Zenodo, 2022)

Experimental Study of the Game Exact Nim(5, 2). - Vladimir Gurvich; Artem Parfenov; Michael N. Vyalyi (CoRR, 2023)

Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements. - Mikhail N. Vyalyi (Probl. Inf. Transm., 2023)

Growing Trees and Amoebas' Replications. - Vladimir Gurvich; Matjaz Krnc; Mikhail N. Vyalyi (CoRR, 2024)

Two-person positive shortest path games have Nash equlibria in pure stationary strategies. - Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Mikhail N. Vyalyi (CoRR, 2024)

Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies. - Endre Boros; Paolo Giulio Franciosa; Vladimir Gurvich; Mikhail N. Vyalyi (Int. J. Game Theory, 2024)

On Universality of Regular Realizability Problems. - Alexander A. Rubtsov; Mikhail N. Vyalyi (Probl. Inf. Transm., 2024)

Computing remoteness functions of Moore, Wythoff, and Euclid's games. - Endre Boros; Vladimir Gurvich; Kazuhisa Makino; Michael N. Vyalyi (Int. J. Game Theory, 2024)

Disjunctive Complexity. - Nikita Ivanov; Alexander A. Rubtsov; Mikhail N. Vyalyi (DCFS, 2025)

Avoidability Beyond Paths. - Vladimir Gurvich; Matjaz Krnc; Martin Milanic; Mikhail N. Vyalyi (Electron. J. Comb., 2025)