default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMikhail N. Vyalyi
Person information
- affiliation: Russian Academy of Sciences, Dorodnitsyn Computing Center, Moscow, Russia
- affiliation: Moscow State University, Russia
- affiliation: National Research University - Higher School of Economics, Moscow, Russia
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Books and Theses
- 2002
[b1]Alexei Y. Kitaev, A. H. Shen, Mikhail N. Vyalyi:
Classical and Quantum Computation. Graduate studies in mathematics 47, American Mathematical Society 2002, ISBN 978-0-8218-3229-5, pp. I-XIII, 1-257
Journal Articles
- 2025
- [j20]Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi:
Avoidability Beyond Paths. Electron. J. Comb. 32(2) (2025) - 2024
- [j19]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): 449-473 (2024) - [j18]Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Michael N. Vyalyi:
Computing remoteness functions of Moore, Wythoff, and Euclid's games. Int. J. Game Theory 53(4): 1315-1333 (2024) - [j17]Alexander A. Rubtsov, Mikhail N. Vyalyi:
On Universality of Regular Realizability Problems. Probl. Inf. Transm. 60(3): 209-232 (2024) - 2023
- [j16]Mikhail N. Vyalyi:
Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements. Probl. Inf. Transm. 59(1): 57-62 (2023) - 2022
- [j15]Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi:
Shifting paths to avoidable ones. J. Graph Theory 100(1): 69-83 (2022) - 2021
- [j14]Vladimir Gurvich, Mikhail N. Vyalyi:
On Computational Hardness of Multidimensional Subtraction Games. Algorithms 14(3): 71 (2021) - [j13]Alexander A. Rubtsov, Mikhail N. Vyalyi:
On computational complexity of set automata. Inf. Comput. 281: 104797 (2021) - [j12]Mikhail N. Vyalyi:
Counting the Number of Perfect Matchings, and Generalized Decision Trees. Probl. Inf. Transm. 57(2): 143-160 (2021) - 2019
- [j11]Mikhail N. Vyalyi, V. K. Leontiev:
Geometry of Translations on a Boolean Cube. Probl. Inf. Transm. 55(2): 152-173 (2019) - 2017
- [j10]Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik:
Grünbaum coloring and its generalization to arbitrary dimension. Australas. J Comb. 67: 119-130 (2017) - [j9]Mikhail N. Vyalyi, I. M. Khuziev:
Fast protocols for leader election and spanning tree construction in a distributed network. Probl. Inf. Transm. 53(2): 183-201 (2017) - 2015
- [j8]Mikhail N. Vyalyi, I. M. Khuziev:
Distributed communication complexity of spanning tree construction. Probl. Inf. Transm. 51(1): 49-65 (2015) - [j7]Mikhail N. Vyalyi, Alexander A. Rubtsov:
On regular realizability problems for context-free languages. Probl. Inf. Transm. 51(4): 349-360 (2015) - 2013
- [j6]Mikhail N. Vyalyi:
On expressive power of regular realizability problems. Probl. Inf. Transm. 49(3): 276-291 (2013) - 2012
- [j5]Vladimir Gurvich, Mikhail N. Vyalyi:
Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs. Discret. Appl. Math. 160(12): 1742-1756 (2012) - 2011
- [j4]Mikhail N. Vyalyi:
On regular realizability problems. Probl. Inf. Transm. 47(4): 342-352 (2011) - 2010
- [j3]Qi Cheng, Sergey P. Tarasov, Mikhail N. Vyalyi:
Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing. Theory Comput. Syst. 46(1): 120-142 (2010) - 2008
- [j2]Sergey P. Tarasov, Mikhail N. Vyalyi:
Semidefinite programming and arithmetic circuit evaluation. Discret. Appl. Math. 156(11): 2070-2078 (2008) - 2005
- [j1]Sergey Bravyi, Mikhail N. Vyalyi:
Commutative version of the local Hamiltonian problem and common eigenspace problem. Quantum Inf. Comput. 5(3): 187-215 (2005)
Conference and Workshop Papers
- 2021
- [c13]Alexander A. Rubtsov, Mikhail N. Vyalyi:
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems. DCFS 2021: 150-162 - 2020
- [c12]Vladimir Gurvich, Mikhail N. Vyalyi:
Computational Hardness of Multidimensional Subtraction Games. CSR 2020: 237-249 - [c11]Dmitry Chistikov, Mikhail N. Vyalyi:
Re-pairing brackets. LICS 2020: 312-326 - 2018
- [c10]Alexander A. Rubtsov, Mikhail N. Vyalyi:
On Emptiness and Membership Problems for Set Automata. CSR 2018: 295-307 - 2017
- [c9]Alexander A. Rubtsov, Mikhail N. Vyalyi:
On Computational Complexity of Set Automata. DLT 2017: 332-344 - 2015
- [c8]Alexander A. Rubtsov, Mikhail N. Vyalyi:
Regular Realizability Problems and Context-Free Languages. DCFS 2015: 256-267 - 2013
- [c7]Mikhail N. Vyalyi:
Universality of Regular Realizability Problems. CSR 2013: 271-282 - 2011
- [c6]Sergey P. Tarasov, Mikhail N. Vyalyi:
Orbits of Linear Maps and Regular Languages. CSR 2011: 305-316 - 2010
- [c5]R. A. Gimadeev, Mikhail N. Vyalyi:
Identical Relations in Symmetric Groups and Separating Words with Reversible Automata. CSR 2010: 144-155 - 2009
- [c4]Mikhail N. Vyalyi:
On Models of a Nondeterministic Computation. CSR 2009: 334-345 - 2007
- [c3]Sergey P. Tarasov, Mikhail N. Vyalyi:
An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity. CSR 2007: 397-406 - 1998
- [c2]Sergey P. Tarasov, Michael N. Vyalyi:
Construction of Contour Trees in 3D in O(n log n) Steps. SCG 1998: 68-75 - 1997
- [c1]Sergey P. Tarasov, Michael N. Vyalyi:
Some PL Functions on Surfaces are not Height Functions. SCG 1997: 113-118
Data and Artifacts
- 2022
- [d1]Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi:
Computer-assisted verification of confining two-rooted graphs with certain cages. Zenodo, 2022
Informal and Other Publications
- 2025
- [i26]Nikita Ivanov, Alexander A. Rubtsov, Mikhail N. Vyalyi:
Disjunctive Complexity. CoRR abs/2503.22997 (2025) - 2024
- [i25]Vladimir Gurvich, Matjaz Krnc, Mikhail N. Vyalyi:
Growing Trees and Amoebas' Replications. CoRR abs/2401.07484 (2024) - [i24]Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Mikhail N. Vyalyi:
Two-person positive shortest path games have Nash equlibria in pure stationary strategies. CoRR abs/2410.09257 (2024) - 2023
- [i23]Endre Boros, Vladimir Gurvich, Kazuhisa Makino, Michael N. Vyalyi:
Computing Remoteness Functions of Moore, Wythoff, and Euclid's games. CoRR abs/2311.02685 (2023) - [i22]Alexander A. Rubtsov, Michael N. Vyalyi:
On universality of regular realizability problems. CoRR abs/2311.15381 (2023) - [i21]Vladimir Gurvich, Artem Parfenov, Michael N. Vyalyi:
Experimental Study of the Game Exact Nim(5, 2). CoRR abs/2311.18772 (2023) - 2022
- [i20]Endre Boros, Paolo Giulio Franciosa, Vladimir Gurvich, Michael N. Vyalyi:
Deterministic n-person shortest path and terminal games on symmetric digraphs have Nash equilibria in pure stationary strategies. CoRR abs/2202.11554 (2022) - [i19]Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi:
Avoidability beyond paths. CoRR abs/2208.12803 (2022) - [i18]Alexander A. Rubtsov, Mikhail N. Vyalyi:
Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems. CoRR abs/2210.03934 (2022) - 2020
- [i17]Vladimir Gurvich, Michael N. Vyalyi:
Computational Hardness of Multidimensional Subtraction Games. CoRR abs/2001.03962 (2020) - [i16]Vladimir Gurvich, Matjaz Krnc, Martin Milanic, Mikhail N. Vyalyi:
Shifting paths to avoidable ones. CoRR abs/2008.01128 (2020) - 2019
- [i15]Alexander Kozachinskiy, Mikhail N. Vyalyi:
Lower bounds on separation automata for Parity Games. CoRR abs/1902.07175 (2019) - [i14]Dmitry Chistikov, Mikhail N. Vyalyi:
Re-pairing brackets. CoRR abs/1904.08402 (2019) - 2017
- [i13]Alexander A. Rubtsov, Mikhail N. Vyalyi:
On computational complexity of Set Automata. CoRR abs/1704.03730 (2017) - [i12]Andrii Riazanov, Mikhail N. Vyalyi:
Exploring the bounds on the positive semidefinite rank. CoRR abs/1704.06507 (2017) - 2016
- [i11]Serge Lawrencenko, Mikhail N. Vyalyi, L. V. Zgonnik:
Grünbaum coloring and its generalization to arbitrary dimension. CoRR abs/1607.03959 (2016) - 2015
- [i10]Alexander A. Rubtsov, Mikhail N. Vyalyi:
Regular realizability problems and context-free languages. CoRR abs/1503.00295 (2015) - [i9]I. M. Khuziev, Michael N. Vyalyi:
Distributed protocols for spanning tree construction and leader election. CoRR abs/1512.01795 (2015) - 2012
- [i8]Mikhail N. Vyalyi:
On complexity of regular realizability problems. CoRR abs/1211.0606 (2012) - 2011
- [i7]Alexander A. Rubtsov, Mikhail N. Vyalyi:
Regular realizability problems and models of a generalized nondeterminism. CoRR abs/1105.5894 (2011) - 2010
- [i6]Sergey P. Tarasov, Mikhail N. Vyalyi:
Orbits of linear maps and regular languages. CoRR abs/1011.1842 (2010) - 2008
- [i5]Mikhail N. Vyalyi:
On models of a nondeterministic computation. CoRR abs/0811.2586 (2008) - 2005
- [i4]Sergey P. Tarasov, Mikhail N. Vyalyi:
Semidefinite programming and arithmetic circuit evaluation. CoRR abs/cs/0512035 (2005) - 2003
- [i3]Michael N. Vyalyi:
Hardness of approximating the weight enumerator of a binary linear code. CoRR cs.CC/0304044 (2003) - [i2]Mikhail N. Vyalyi:
QMA=PP implies that PP contains PH. Electron. Colloquium Comput. Complex. TR03 (2003) - 2001
- [i1]Michael N. Vyalyi:
A comparison of Zeroes and Ones of a Boolean Polynomial. CoRR cs.CC/0111052 (2001)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-06-16 23:58 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
