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.

[BibT_eX]

[DOI]

Endre Boros

Paolo Giulio Franciosa

Int. J. Game Theory, June, 2024

Two-person positive shortest path games have Nash equlibria in pure stationary strategies.

[BibT_eX]

[DOI]

CoRR, 2024

Growing Trees and Amoebas' Replications.

[BibT_eX]

[DOI]

Matjaz Krnc

CoRR, 2024

2023

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

[BibT_eX]

[DOI]

Probl. Inf. Transm., January, 2023

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

[BibT_eX]

[DOI]

Artem Parfenov

CoRR, 2023

2022

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

[BibT_eX]

[DOI]

Dataset, August, 2022

Shifting paths to avoidable ones.

[BibT_eX]

[DOI]

J. Graph Theory, 2022

Avoidability beyond paths.

[BibT_eX]

[DOI]

CoRR, 2022

2021

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

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2021

On computational complexity of set automata.

[BibT_eX]

[DOI]

Inf. Comput., 2021

On Computational Hardness of Multidimensional Subtraction Games.

[BibT_eX]

[DOI]

Algorithms, 2021

Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2021

2020

Re-pairing brackets.

[BibT_eX]

[DOI]

Dmitry Chistikov

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

2019

Geometry of Translations on a Boolean Cube.

[BibT_eX]

[DOI]

V. K. Leontiev

Probl. Inf. Transm., 2019

Lower bounds on separation automata for Parity Games.

[BibT_eX]

[DOI]

Alexander Kozachinskiy

CoRR, 2019

2018

On Emptiness and Membership Problems for Set Automata.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

2017

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

[BibT_eX]

[DOI]

I. M. Khuziev

Probl. Inf. Transm., 2017

Exploring the bounds on the positive semidefinite rank.

[BibT_eX]

[DOI]

Andrii Riazanov

CoRR, 2017

Grünbaum coloring and its generalization to arbitrary dimension.

[BibT_eX]

[DOI]

Serge Lawrencenko

L. V. Zgonnik

Australas. J Comb., 2017

2015

On regular realizability problems for context-free languages.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2015

Distributed communication complexity of spanning tree construction.

[BibT_eX]

[DOI]

I. M. Khuziev

Probl. Inf. Transm., 2015

Distributed protocols for spanning tree construction and leader election.

[BibT_eX]

[DOI]

I. M. Khuziev

CoRR, 2015

Regular Realizability Problems and Context-Free Languages.

[BibT_eX]

[DOI]

Proceedings of the Descriptional Complexity of Formal Systems, 2015

2013

On expressive power of regular realizability problems.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2013

Universality of Regular Realizability Problems.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2013

2012

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

[BibT_eX]

[DOI]

Discret. Appl. Math., 2012

On complexity of regular realizability problems

[BibT_eX]

[DOI]

CoRR, 2012

2011

On regular realizability problems.

[BibT_eX]

[DOI]

Probl. Inf. Transm., 2011

Regular realizability problems and models of a generalized nondeterminism

[BibT_eX]

[DOI]

CoRR, 2011

Orbits of Linear Maps and Regular Languages.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2011

2010

Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing.

[BibT_eX]

[DOI]

Qi Cheng

Theory Comput. Syst., 2010

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

[BibT_eX]

[DOI]

R. A. Gimadeev

Proceedings of the Computer Science, 2010

2009

On Models of a Nondeterministic Computation.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2009

2008

Semidefinite programming and arithmetic circuit evaluation.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

2007

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

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2007

2005

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

[BibT_eX]

[DOI]

Sergey Bravyi

Quantum Inf. Comput., 2005

2003

QMA=PP implies that PP contains PH

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Hardness of approximating the weight enumerator of a binary linear code

[BibT_eX]

[DOI]

CoRR, 2003

2002

Classical and Quantum Computation.

[BibT_eX]

[DOI]

Alexei Y. Kitaev

A. H. Shen

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

[BibT_eX]

[DOI]

CoRR, 2001

1998

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

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998

1997

Some PL Functions on Surfaces are not Height Functions.

[BibT_eX]

[DOI]