Малышев Дмитрий Сергеевич, профессор кафедры прикладной математики и информатики, ведущий научный сотрудник Лаборатория алгоритмов и технологий анализа сетевых структур (Нижний Новгород)

НОМИНАЦИЯ «ДОСТИЖЕНИЕ В НАУКЕ»

Кандидатуру предлагает коллектив Лаборатории алгоритмов и технологий анализа сетевых структур

Малышев Дмитрий Сергеевич – блестящий  ученый с высокой научной репутацией. Работает в НИУ ВШЭ в Нижнем Новгороде с 2010 года. В 2014 году, в возрасте 28 лет, он защитил докторскую диссертацию в МГУ им. М.В.Ломоносова, став одним из самых молодых докторов физико-математических наук. Несмотря на молодость, он является одним из ведущих российских специалистов в области алгоритмической теории графов, автором более 60 работ в ведущих международных и российских журналах по этой тематике. После защиты докторской диссертации Малышев Д.С. не только сохранил, но и  значительно увеличил свою научную активность. Только за последние 3 года (2016-2018) им опубликовано 16 статей в международных журналах квартилей Q1-Q2 (6 уровня Q1 и 10 уровня Q2). Дмитрий Сергеевич успешно руководит научными проектами. Он являлся руководителем трех грантов РФФИ, двух грантов Президента РФ для молодых российских ученых, гранта по программе ФЦП «Кадры»,  индивидуальных грантов научного фонда НИУ ВШЭ. По результатам Конкурса проектов фундаментальных научных исследований, выполняемых молодыми учеными в научных организациях Российской Федерации, Малышев Д.С. получил поддержку РФФИ на выполнение индивидуальных научных исследований.  В 2016-2018 гг. Коллектив молодых ученых под руководством Дмитрия Малышева выиграл грант РФФИ «стабильность» для продолжения исследований в 2019-2020 гг.  Решением Президиума РАН в декабре 2015 г. Малышеву Д.С. присуждена медаль Российской академии наук в области математики. Решением Российского клуба членов Европейской Академии в декабре 2017 г. ему была присуждена медаль Европейской Академии в области математики. 

В работах Малышева Д.С. развивается оригинальный подход к исследованию вычислительной сложности задач на графах, основанный на понятии критического класса графов. Критические классы графов  позволяют выразить сложность задачи в «топологических» терминах и описать явление «фазового перехода» в оценках сложности.  Знания всех критических классов графов достаточно для полной классификации сложности рассматриваемых задач в ряде важных семейств классов графов. В работах Малышева Д.С. в 2010-2018 гг. получены окончательные ответы на ряд принципиальных и ранее открытых вопросов существования и полноты в теории критических классов, а также разработаны перспективные методы  редукции графов, полезные для построения полиномиальных алгоритмов решения дискретных экстремальных задач на графах. Исследования Малышева Д.С. носят пионерский характер. Обычно используется подход, связанный с исследованием сложности задачи на графах в «классических» классах графов. Однако, при всей важности такого рода исследований, этот подход не позволяет объяснить, с чем связана смена сложности задачи при тех или иных сужениях множества всех графов. Подход, применяемый Малышевым Д.С., позволяет это сделать.    

Научную работу Малышев Д.С. успешно сочетает с экспертной и общественной деятельностью в области науки, являясь экспертом ряда научных фондов, рецензентом и референтом научных и реферативных журналов. 

Малышев Д.С. – отличный педагог, проводит занятия творчески, добиваясь высокого результата в усвоении сложного материала студентами. В своей работе старается прививать студентам высокую культуру математического мышления, сохраняя лучшие традиции российского образования. Им были разработаны оригинальные программы курсов для студентов направления ПМИ, содержание которых он компетентно и заинтересованно передает студентам. В 2016 и 2018 гг. Малышев Д.С. был выбран лучшим преподавателем направления ПМИ. Успешно руководит выпускными квалификационными работами бакалавров и магистров, группой исследователей в международной лаборатории ЛАТАС. Его ученики принимают деятельное участие в научных проектах и публикуются в международных и центральных российских журналах. Под руководством Малышева Д.С. подготовлена и успешно в 2016 году защищена кандидатская диссертация, а также в 2017 году «высижен» «серебряный птенец». Малышев Д.С. характеризуется исследовательской и творческой целеустремленностью, инициативностью и ответственностью, трудолюбием и высокой работоспособностью, неравнодушием к студентам и коллегам.

Публикации Малышева Д.С. в международных журналах  за 2016-2018 гг.

2018

• D. V. Gribanov, D.S. Malyshev, P. M. Pardalos, Veselov S. I. FPT-algorithms for some problems related to integer programming // Journal of Combinatorial Optimization. 2018. Vol. 35. No. 4. P. 1128-1146 (Q2 WOS,Scopus).
• Malyshev D., Gribanov D. The computational complexity of dominating set problems for instances with bounded minors of constraint matrices // Discrete Optimization. 2018. Vol. 29. P. 103-110 (Q2 Scopus).
• Malyshev D. The weighted coloring problem for two graph classes characterized by small forbidden induced structures // Discrete Applied Mathematics. 2018. Vol. 247. P. 423-432 (Q2 Scopus).
• Vladislav Kruglov, Dmitry Malyshev, Olga Pochinka. Topological Classification of Ω-stable Flows on Surfaces by Means of Effectively Distinguishable Multigraphs // Discrete and Continuous Dynamical Systems. 2018. Vol. 38. No. 9. P. 4305-4327 (Q1 WOS,Scopus).

2017

• Lozin V. V., Malyshev D., Mosca R., Zamaraev V. A. More results on weighted independent domination // Theoretical Computer Science. 2017. Vol. 700. P. 63-74 (Q1 Scopus).
• Malyshev D. Polynomial-time approximation algorithms for the coloring problem in some cases // Journal of Combinatorial Optimization. 2017. Vol. 33. No. 3. P. 809-813 (Q2 WOS,Scopus).
• Malyshev D. The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs // Graphs and Combinatorics. 2017. Vol. 33. No. 4. P. 1009-1022 (Q2 Scopus).
•  Gribanov D., Malyshev D. The computational complexity of three graph problems for instances with bounded minors of constraint matrices // Discrete Applied Mathematics. 2017. Vol. 227. P. 13-20 (Q2 Scopus).
• Turkensteen M., Malyshev D., Goldengorin B. I., Pardalos P. M. The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems // Journal of Global Optimization. 2017. Vol. 68. No. 3. P. 601-622 (Q1 WoS, Scopus)
• Malyshev D., Lobanova O. O. Two complexity results for the vertex coloring problem // Discrete Applied Mathematics. 2017. Vol. 219. P. 158-166 (Q2 Scopus).
• Lozin V. V., Malyshev D. Vertex coloring of graphs with few obstructions // Discrete Applied Mathematics. 2017. Vol. 216. P. 273-280 (Q2 Scopus).

2016

• Malyshev D. A complexity dichotomy and a new boundary class for the dominating set problem // Journal of Combinatorial Optimization. 2016. Vol. 32. No. 1. P. 226-243 (Q2 Wos,Scopus).
• Malyshev D. A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs // Discrete Applied Mathematics. 2016. Vol. 203. P. 117-126 (Q1 Scopus).
• Malyshev D., Pardalos P. M. Critical hereditary graph classes: a survey // Optimization Letters. 2016. Vol. 10. No. 8. P. 1593-1612 (Q1 Scopus).
• Grines V., Malyshev D., Pochinka O., Zinina S. Efficient algorithms for the recognition of topologically conjugate gradient-like diffeomorhisms // Regular and Chaotic Dynamics. 2016. Vol. 21. No. 2. P. 189-203 (Q1, Scopus).
• Malyshev D. Two cases of polynomial-time solvability for the coloring problem // Journal of Combinatorial Optimization. 2016. Vol. 31. No. 2. P. 833-845 (Q2 WOS, Scopus).