Список публикаций в обратном хронологическом порядке

• Orbits of linear maps and regular languages. (соавтор С.П.Тарасов) E-print, 2010. arXiv:1011.1842v2.
• Орбиты линейных отображений и свойства регулярных языков. (соавтор С.П.Тарасов) Дискр. анализ и иссл. операций, 2010. Т. 17, № 6. С. 20-49.
• Дискретный анализ. Формальные системы и алгоритмы. (соавторы Журавлёв Ю.И., Флёров Ю.А.) М.: ООО Контакт Плюс, 2010.
• Identical relations in symmetric groups and separating words with reversible automata. (соавтор R.A.Gimadeev) Proc. of CSR 2010. Springer Lecture Notes in Computer Science, vol. 6072, 2010. P. 144-155.
• Задача о тождествах в симметрической группе и ее приложения. (соавтор Р.А. Гимадеев) Материалы X Международного семинара “Дискретная математика и ее приложения”, М.: МГУ, 2010. С.250-251.
• Efficient Algorithms for Sparse Cyclotomic Integer Zero Testing. (соавторы Qi Cheng, S. Tarasov) Theory of Computing Systems. V.46. 2010. P. 120-142.
• О моделях недетерминизма для двусторонних автоматов. Труды VIII международной конференции “Дискретные модели в теории управляющих систем”. М.: МаксПресс, 2009. С. 54-60.
• Фуксовы группы: от топологии к геометрии. (соавтор О.В.Шварцман) Математическое просвещение, сер.3, вып. 13. 2009. С. 33-49.
• On models of a nondeterministic computation. Springer Lecture Notes in Computer Science, vol. 5675, 2009. P. 334-345.
• On models of a nondeterministic computation. 2008. arXiv:0811.2586
• Semidefinite programming and arithmetic circuit evaluation. (соавтор Тарасов С.П.) Discrete Applied Mathematics, 2008. Vol. 156, p. 2070-2078.
• Обобщенный пример К.Мурти и “линейная” гипотеза Хирша (соавтор Тарасов С.П.) // Материалы IX Международного семинара “Дискретная математика и её приложения”, посвящённого 75-летию со дня рождения академика О.Б. Лупанова, Москва, 18-23 июня, 2007. - С. 372-373.
• An efficient algorithm for zero-testing of a lacunary polynomial at the roots of unity (соавтор Тарасов С.П.) // Springer, Lecture notes in Computer Science, No 4649. 2007. P. 397-406.
• О сложности операций с числами, представленными арифметическими схемами. (соавтор Тарасов С.П.) // Труды VII международной конференции “Дискретные модели в теории управляющих систем”. М.: МГУ, 2006. С. 82-87.
• Дискретный анализ. Основы высшей алгебры. (соавторы Журавлёв Ю.И., Флёров Ю.И.) М.: МЗ Пресс, 2006. Изд. 2е, расш. 2007.
• О представлении чисел в виде суммы двух квадратов. // Математическое просвещение, сер. 3, вып. 10, 2006. С. 190-194.
• Semidefinite programming and arithmetic circuit evaluation. (соавтор Тарасов С.П.) 2005. xxx.lanl.gov/cs.CC/0512035
• Commutative version of the local Hamiltonian problem and common eigenspace problem. (соавтор Бравый С.) // Quantum information and computation, 2005. Vol. 5, no 3. P. 187-215.
• Кратчайшие пути по поверхности параллелепипеда. // Математическое просвещение, сер. 3, вып. 9, 2005. С. 203-206.
• Пфаффианы или искусство расставлять знаки. // Математическое просвещение, сер. 3, вып. 9, 2005. С. 129-142.
• Задачи о вхождении подслова в таблицу значений булевого полинома. // Материалы VIII Международного семинара "Дискретная математика и ее приложения". М.: МГУ, 2004. С. 125-126.
• Приближенное вычисление весовой функции линейного двоичного кода. // Дискр. анализ и иссл. операций, 2004. Сер.1, т.11, №4, с.3-19.
• Алгоритмические задачи с таблицами значений булевых полиномов. // Труды ИСП РАН, т.6, 2004. С. 51-64.
• Проблемы теории сложности квантовых вычислений. (соавтор Н.П.Варновский) // Московский университет и развитие криптографии в России. М.: МЦНМО, 2003. С.207-234.
• Линейные неравенства и комбинаторика. М.: МЦНМО, 2003.
• Hardness of approximating the weight enumerator of a binary linear code. 2003. xxx.lanl.gov/cs.CC/0304044
• Commutative version of k-local Hamiltonian problem and non-triviality check for quantum codes. (соавтор Бравый С.) 2003. xxx.lanl.gov/quant-ph/0308021
• QMA=PP implies that PP contains PH. ECCC, 2003. TR03-21.
• Classical and quantum computation. (соавторы: Китаев А.Ю., Шень А.) AMS, 2002.
• Монотонные булевы полиномы. (соавторы Леонтьев В.К., Осетров М.В.) // Дискретный анализ и исследование операций, 2002. Сер.1. Т.9, № 4. С.41-49.
• О числе решений уравнений в словах. (соавтор Тарасов С.П.) // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции, 2002. С. 40.
• Ю.Романов. Интервью с Михаилом Вялым. Компьютерра, №27, 15.07.2002
• Случайность как вычислительный ресурс Компьютерра, № 10, 18.03.2002
• Какая математика нужна для алгоритмов? Компьютерра, № 10, 18.03.2002
• A comparison of zeroes and ones of a Boolean Polynomial. 2001. xxx.lanl.gov/cs.CC/0111052
• Нейрооптимизм. Компьютерра, 08.02.2000.
• Сложность вычислительных задач. // Математическое просвещение, сер.3, вып. 4, 2000. С.81-114.
• Парабола как окружность. // Десятая летняя конференция Турнира Городов. М.: МЦНМО, 1999. С. 36-42, 112-123.
• Классические и квантовые вычисления. (соавторы: Китаев А.Ю., Шень А.) М.: МЦНМО-ЧеРо, 1999.
• Construction of Contour Trees in 3D in O(n log n) steps. (соавтор Тарасов С.П.) // Proceedings 14th Annual ACM Symposium on Computational Geometry, 1998. P. 68-75.
• Some PL functions on surfaces are not height functions. (соавтор Тарасов С.П.) // Proceedings 13th Annual ACM Symposium on Computational Geometry, 1997. P. 113-118.
• Ключевые слова: квантовые вычисления (беседа с Л.И. Левковичем-Маслюком) Компьютерра, № 47, 24.11.1997.
• О вложениях булева куба в графы ограниченной степени. // Комбинаторные модели и методы-2. М.: ВЦ РАН, 1997. С.~5--9.
• О порядковом роде. (соавтор Тарасов С.П.) // Комбинаторные модели и методы-2. М.: ВЦ РАН, 1997. С.~25-43.
• Об алгоритмической сложности задач, связанных с вычислением частичных сумм. // Методы комбинаторной оптимизации. М.: ВЦ РАН, 1997. С.~5-11.
• Сортировка переворотами. // Седьмая летняя конференция Турнира Городов. М.: ИЦТГ, 1996. С. 29-31, 86-95.
• Об устойчивости диаграммы Вороного. (соавторы Гордеев Э.Н., Тарасов С.П.) // ЖВМиМФ, 1996. Т.36, № 3. С. 147-158.
• (рук.) Геометрия комбинаторных многогранников. Диссертация на соискание ученой степени кандидата физико-математических наук. М.: ВЦ РАН, 1995.
• Об оценках значений функционала в многогранниках задачи ПОДГРАФ НАИМЕНЬШЕГО ВЕСА. // Комбинаторные модели и методы. М.: ВЦ РАН, 1995. С. 27-43.
• О неразложимых графах. // Комбинаторные модели и методы. М.: ВЦ РАН, 1995. С. 61-66.
• Квадратичные рекуррентные последовательности и оценки числа монотонных булевых функций для некоторых порядков. (соавтор Соколов Н.А.) // Комбинаторные модели и методы. М.: ВЦ РАН, 1995. С. 44-54.
• Перечисление идеалов некоторых простых порядков. (соавтор Соколов Н.А.) // Комбинаторные модели и методы. ВЦ РАН, 1995. С. 55-60.
• Сети. // Четвертая конференция Турнира Городов. М.: ИЦТГ, 1993. С. 11-13, 33-46.
• Алгоритмы локальной оптимизации и геометрия многогранников. // Комбинаторные модели и методы. М.: ВЦ РАН, 1995. С. 15-26.
• Об одномерных проекциях многогранников задач дискретной оптимизации. // Дискретная математика, 1991. Т. 3, №3. С. 35-45.
• О принципах построения и реализации систем 3-мерного геометрического моделирования. (соавтор: Леонов В.Ю.) // Моделирование и экспертные системы. М.: МИРЭА, 1989. C. 39-47.