Michael Vyalyi

2022¹

2021⁶

• Chapter Rubtsov A. A., Vyalyi M. Automata Equipped with Auxiliary Data Structures and Regular Realizability Problems, in: Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings. Springer, 2021. P. 150-162. doi
• Article Vyalyi M. Counting the Number of Perfect Matchings, and Generalized Decision Trees // Problems of Information Transmission. 2021. Vol. 57. No. 2. P. 143-160. doi
• Article Chikin N., Gurvich V., Knop K., Paterson M., Vyalyi M. More about Exact Slow k-Nim // Integers. Electronic Journal of Combinatorial Number Theory. 2021. Vol. 21. P. 1-14.
• Article Rubtsov A. A., Vyalyi M. On computational complexity of set automata // Information and Computation. 2021. Vol. 281. Article 104797. doi
• Article Ключиков А. Г., Вялый М. Н. Win-win алгоритм для задачи (k+1)-LST/k-путевого представления // Дискретный анализ и исследование операций. 2021. Т. 28. № 4. С. 117-124. doi
• 
  Book Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А., Шень А. Лекции по дискретной математике. М. : Издательский дом НИУ ВШЭ, 2021. doi

2020²

• Chapter Gurvich V., Vyalyi M. Computational hardness of multidimensional subtraction games, in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, Proceedings Vol. 12159. Springer, 2020. doi P. 237-249. doi
• Chapter Chistikov D., Mikhail Vyalyi. Re-pairing brackets, in: LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. Saarbrücken, Germany. July, 2020. Association for Computing Machinery (ACM), 2020. P. 312-326. doi

2019²

• Article Vyalyi M., Леонтьев В. К. Geometry of Translations on a Boolean Cube / Пер. с рус. // Problems of Information Transmission. 2019. Vol. 55. No. 2. P. 152-173. doi
• Book Вялый М. Н., Подольский В. В., Рубцов А. А., Шварц Д. А., Шень А. Лекции по дискретной математике. Издательский дом НИУ ВШЭ, 2019. (in press)

2018²

• Chapter Rubtsov A. A., Vyalyi M. On Emptiness and Membership Problems for Set Automata, in: Computer Science – Theory and Applications 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018, Proceedings / Ed. by F. V. Fomin, V. V. Podolskii. Vol. 10846. Springer, 2018. doi P. 295-307. doi
• Chapter Вялый М. Н. Сложность вычисления знака перестановки в модели разрешающих деревьев и подсчет совершенных паросочетаний в двудольных графах // В кн.: Труды X международной конференции "Дискретные модели в теории управляющих систем". Москва и Подмосковье, 23-25 мая 2018 г. / Отв. ред.: В. Алексеев, Д. Романов, Б. Данилов. М. : МАКС Пресс, 2018. С. 94-97.

2017⁵

• Article M.N.Vyalyi, Khuziev I. Fast protocols for leader election and spanning tree construction in a distributed network / Пер. с рус. // Problems of Information Transmission. 2017. Vol. 53. No. 2. P. 183-201. doi
• Article M.N.Vyalyi, Lawrencenko S., Zgonnik L. Grunbaum coloring and its generalization to arbitrary dimension // Australasian Journal of Combinatorics. 2017. Vol. 67. No. 2. P. 119-130.
• Article Voronenko A. A., Mikhail N. Vyalyi. Lower estimate for the cardinality of the domain of universal functions for the class of linear Boolean functions / Пер. с рус. // Discrete Mathematics and Applications. 2017. P. 319-324. doi
• Chapter Rubtsov A. A., Vyalyi M. On Computational Complexity of Set Automata, in: Developments in Language Theory 21st International Conference, DLT 2017, Liège, Belgium, August 7-11, 2017, Proceedings. Cham : Springer, 2017. doi P. 332-344. doi
• Article M.N.Vyalyi, Babenko A. On the linear classification of even and odd permutation matrices and the complexity of computing the permanent / Пер. с рус. // Computational Mathematics and Mathematical Physics. 2017. Vol. 57. No. 2. P. 362-371. doi

2016¹

2015³

• Chapter Rubtsov A. A., Vyalyi M. Regular Realizability Problems and Context- Free Languages, in: Descriptional Complexity of Formal Systems Vol. 9118. Switzerland : Springer, 2015. doi P. 256-267.
• Article Вялый М. Н., Рубцов А. А. О задачах регулярной реализуемости для контекстно-свободных языков // Проблемы передачи информации. 2015. Т. 51. № 4. С. 47-59. doi
• Article Вялый М. Н., Хузиев И. М. Распределенная коммуникационная сложность построения остовного дерева // Проблемы передачи информации. 2015. Т. 51. № 1. С. 54-71. doi

2014²

• Article Vyalyi M., Gimadeev R. Separating words by occurrences of subwords / Пер. с рус. // Journal of Applied and Industrial Mathematics. 2014. Vol. 8. No. 2. P. 293-299.
• Article Вялый М. Н., Гимадеев Р. О различении слов вхождениями подслов // Дискретный анализ и исследование операций. 2014. Т. 21. № 1. С. 3-14.

2013³

• Article Vyalyi M. Universality of regular realizability problems // Lecture Notes in Computer Science. 2013. Vol. 7913. P. 271-282.
• Article Вялый М. Н. Конусы полистепеней и задачи комбинаторной оптимизации // Журнал вычислительной математики и математической физики. 2013. Т. 53. № 5. С. 816-824.
• Article Вялый М. Н. О выразительной силе задач регулярной реализуемости // Проблемы передачи информации. 2013. Т. 49. № 3. С. 86-104.

2012³

• Article Gurvich V., Vyalyi M. Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs // Discrete Applied Mathematics. 2012. Vol. 160. P. 1742-1756.
• Article Вялый М. Н., Рубцов А. А. Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах // Дискретный анализ и исследование операций. 2012
• Article Вялый М. Н., Гурвич В. Ультраметрики, потоки, деревья и узкие места // Математическое просвещение. 2012. № 16. С. 75-88.

2011³

• Article Vyalyi M., Tarasov S. Orbits of Linear Maps and Regular Languages // Journal of Applied and Industrial Mathematics. 2011. Vol. 5. No. 3. P. 448-465.
• Article Vyalyi M., Tarasov S. Orbits of linear maps and regular languages // Lecture Notes in Computer Science. 2011. Vol. 6651. P. 305-316.
• Article Вялый М. Н. О задачах регулярной реализуемости // Проблемы передачи информации. 2011. Т. 47. № 4. С. 43-54.

2010⁴

• Article Vyalyi M., Cheng Q., Tarasov S. Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing // Theory of Computing Systems. 2010. Vol. 46. P. 120-142.
• Article Vyalyi M., Gimadeev R. Identical relations in symmetric groups and separating words with reversible automata // Lecture Notes in Computer Science. 2010. Vol. 6072. P. 144-155.
• Book Журавлев Ю., Флёров Ю., Вялый М. Н. Дискретный анализ. Формальные системы и алгоритмы. М. : ООО "Контакт Плюс", 2010.
• Article Вялый М. Н., Тарасов С. Орбиты линейных отображений и свойства регулярных языков // Дискретный анализ и исследование операций. 2010. Т. 17. № 6. С. 20-49.

2009²

• Article Vyalyi M. On models of a nondeterministic computation // Lecture Notes in Computer Science. 2009. Vol. 5675. P. 334-345.
• Article Вялый М. Н., Шварцман О. Фуксовы группы: от топологии к геометрии // Математическое просвещение. 2009. № 13. С. 33-49.

2008²

• Book Вялый М. Н., Семенов А., Ландо С. К. Информатика-7. Алгоритмика. М. : Просвещение, 2008.
• Article Vyalyi M., Tarasov S. Semidefinite programming and arithmetic circuit evaluation // Discrete Applied Mathematics. 2008. Vol. 156. P. 2070-2078.

2006³

• Book Журавлев Ю., Флёров Ю., Вялый М. Н. Дискретный анализ. Основы высшей алгебры. М. : МЗ Пресс, 2006.
• Article Вялый М. Н. О представлении чисел в виде суммы двух квадратов // Математическое просвещение. 2006. № 10. С. 190-194.
• Chapter Вялый М. Н., Тарасов С. О сложности операций с числами, представленными арифметическими схемами // В кн.: Труды VII международной конференции "Дискретные модели в теории управляющих систем". М. : МГУ, 2006. С. 82-87.

2005³

• Article Vyalyi M., Bravyi S. Commutative version of the local Hamiltonian problem and common eigenspace problem // Quantum information and computation. 2005. Vol. 5. No. 3. P. 187-215.
• Article Вялый М. Н. Кратчайшие пути по поверхности параллелепипеда // Математическое просвещение. 2005. № 9. С. 203-206.
• Article Вялый М. Н. Пфаффианы или искусство расставлять знаки // Математическое просвещение. 2005. Т. 11. № 9. С. 129-142.

2004⁴

• Article Вялый М. Н. Алгоритмические задачи с таблицами значений булевых полиномов // Труды Института системного программирования РАН. 2004. Т. 6. С. 51-64.
• Chapter Вялый М. Н. Задачи о вхождении подслова в таблицу значений булева полинома // В кн.: Материалы VIII Международного семинара "Дискретная математики и ее приложения". М. : МГУ, 2004. С. 125-126.
• Article Вялый М. Н. Приближенное вычисление весовой функции линейного двоичного кода // Дискретный анализ и исследование операций. 2004. Т. 11. № 4. С. 3-19.
• Chapter Вялый М. Н. Приближенное вычисление весовой функции линейного двоичного кода // В кн.: Материалы конференции "Дискретный анализ и исследование операций" 2004. Новосибирск : Институт математики им. С.Л. Соболева СО РАН, 2004.

2003²

• Book Вялый М. Н. Линейные неравенства и комбинаторика. М. : МЦНМО, 2003.
• Chapter Вялый М. Н., Варновский Н. Проблемы теории сложности квантовых вычислений // В кн.: Московский университет и развитие криптографии в России. Материалы конференции МГУ 17-18 октября 2002 г. М. : МЦНМО, 2003. С. 207-234.

2002³

• Book Kitaev A. Y., Shen A. H., Vyalyi M. Classical and quantum computation. AMS, 2002.
• Article Вялый М. Н., Леонтьев В., Осетров М. Монотонные булевы полиномы // Дискретный анализ и исследование операций. 2002. Т. 9. № 4. С. 41-49.
• Chapter Вялый М. Н., Тарасов С. О числе решений уравнений в словах // В кн.: Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции. М. : Издательство центра прикладных исследований при механико-математическом факультете МГУ, 2002.

1999¹

1998¹

1997¹

1996¹

1991¹

1989¹