Mikhail N. Vyalyi

According to our database, Mikhail N. Vyalyi authored at least 44 papers between 1997 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Computing remoteness functions of Moore, Wythoff, and Euclid's games.

Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Michael N. Vyalyi

Int. J. Game Theory, December, 2024

On Universality of Regular Realizability Problems.

Alexander A. Rubtsov, Mikhail N. Vyalyi

Probl. Inf. Transm., September, 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, June, 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

Growing Trees and Amoebas' Replications.

Vladimir Gurvich, Matjaz Krnc, Mikhail N. Vyalyi

CoRR, 2024

2023

Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements.

Mikhail N. Vyalyi

Probl. Inf. Transm., January, 2023

Experimental Study of the Game Exact Nim(5, 2).

Vladimir Gurvich, Artem Parfenov, Michael N. Vyalyi

CoRR, 2023

2022

Computer-assisted verification of confining two-rooted graphs with certain cages.

Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi

Dataset, August, 2022

Shifting paths to avoidable ones.

Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi

J. Graph Theory, 2022

Avoidability beyond paths.

Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi

CoRR, 2022

2021

Counting the Number of Perfect Matchings, and Generalized Decision Trees.

Mikhail N. Vyalyi

Probl. Inf. Transm., 2021

On computational complexity of set automata.

Alexander A. Rubtsov, Mikhail N. Vyalyi

Inf. Comput., 2021

On Computational Hardness of Multidimensional Subtraction Games.

Vladimir Gurvich, Mikhail N. Vyalyi

Algorithms, 2021

Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems.

Alexander A. Rubtsov, Mikhail N. Vyalyi

Proceedings of the Descriptional Complexity of Formal Systems, 2021

2020

Re-pairing brackets.

Dmitry Chistikov, Mikhail N. Vyalyi

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

2019

Geometry of Translations on a Boolean Cube.

Mikhail N. Vyalyi, V. K. Leontiev

Probl. Inf. Transm., 2019

Lower bounds on separation automata for Parity Games.

Alexander Kozachinskiy, Mikhail N. Vyalyi

CoRR, 2019

2018

On Emptiness and Membership Problems for Set Automata.

Alexander A. Rubtsov, Mikhail N. Vyalyi

Proceedings of the Computer Science - Theory and Applications, 2018

2017

Fast protocols for leader election and spanning tree construction in a distributed network.

Mikhail N. Vyalyi, I. M. Khuziev

Probl. Inf. Transm., 2017

Exploring the bounds on the positive semidefinite rank.

Andrii Riazanov, Mikhail N. Vyalyi

CoRR, 2017

Grünbaum coloring and its generalization to arbitrary dimension.

Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik

Australas. J Comb., 2017

2015

On regular realizability problems for context-free languages.

Mikhail N. Vyalyi, Alexander A. Rubtsov

Probl. Inf. Transm., 2015

Distributed communication complexity of spanning tree construction.

Mikhail N. Vyalyi, I. M. Khuziev

Probl. Inf. Transm., 2015

Distributed protocols for spanning tree construction and leader election.

I. M. Khuziev, Michael N. Vyalyi

CoRR, 2015

Regular Realizability Problems and Context-Free Languages.

Alexander A. Rubtsov, Mikhail N. Vyalyi

Proceedings of the Descriptional Complexity of Formal Systems, 2015

2013

On expressive power of regular realizability problems.

Mikhail N. Vyalyi

Probl. Inf. Transm., 2013

Universality of Regular Realizability Problems.

Mikhail N. Vyalyi

Proceedings of the Computer Science - Theory and Applications, 2013

2012

Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs.

Vladimir Gurvich, Mikhail N. Vyalyi

Discret. Appl. Math., 2012

On complexity of regular realizability problems

Mikhail N. Vyalyi

CoRR, 2012

2011

On regular realizability problems.

Mikhail N. Vyalyi

Probl. Inf. Transm., 2011

Regular realizability problems and models of a generalized nondeterminism

Alexander A. Rubtsov, Mikhail N. Vyalyi

CoRR, 2011

Orbits of Linear Maps and Regular Languages.

Sergey P. Tarasov, Mikhail N. Vyalyi

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing.

Qi Cheng, Sergey P. Tarasov, Mikhail N. Vyalyi

Theory Comput. Syst., 2010

Identical Relations in Symmetric Groups and Separating Words with Reversible Automata.

R. A. Gimadeev, Mikhail N. Vyalyi

Proceedings of the Computer Science, 2010

2009

On Models of a Nondeterministic Computation.

Mikhail N. Vyalyi

Proceedings of the Computer Science, 2009

2008

Semidefinite programming and arithmetic circuit evaluation.

Sergey P. Tarasov, Mikhail N. Vyalyi

Discret. Appl. Math., 2008

2007

An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity.

Sergey P. Tarasov, Mikhail N. Vyalyi

Proceedings of the Computer Science, 2007

2005

Commutative version of the local Hamiltonian problem and common eigenspace problem.

Sergey Bravyi, Mikhail N. Vyalyi

Quantum Inf. Comput., 2005

2003

QMA=PP implies that PP contains PH

Mikhail N. Vyalyi

Electron. Colloquium Comput. Complex., 2003

Hardness of approximating the weight enumerator of a binary linear code

Michael N. Vyalyi

CoRR, 2003

2002

Classical and Quantum Computation.

Alexei Y. Kitaev, A. H. Shen, Mikhail N. Vyalyi

Graduate studies in mathematics 47, American Mathematical Society, ISBN: 978-0-8218-3229-5, 2002

2001

A comparison of Zeroes and Ones of a Boolean Polynomial

Michael N. Vyalyi

CoRR, 2001

1998

Construction of Contour Trees in 3D in O(n log n) Steps.

Sergey P. Tarasov, Michael N. Vyalyi

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997

Some PL Functions on Surfaces are not Height Functions.

Sergey P. Tarasov, Michael N. Vyalyi

Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997