О конкретных новых результатах я регулярно рассказываю на своей странице в Контакте, подписывайтесь!

А если в общих словах и не считать недавние отступления в историю математики , то большая часть моих исследований укладывается в тему параметризованной теории сложности: это многомерный подход к анализу сложности вычислительных задач, который измеряет сложность не только относительно объёма входных данных, но и относительно других параметров. Это позволяет отвечать, например, на следующие вопросы:

1. Как эффективно и оптимально решать NP-трудные задачи оптимизации? Многие задачи комбинаторной оптимизации относятся к так называемым NP-трудным задачам. Например: отыскание кратчайшего обхода заданного подмножества вершин или рёбер графа, отыскание кратчайшего расписания для выполнения проекта, или оптимальная кластеризация данных.

Решение NP-трудных задач, как правило, требует времени, зависящего экспоненциально от объёма входных данных. На практике алгоритмы с такой трудоёмкостью неприемлемы даже при малых объёмах данных, так что о модных "больших данных" в этом контексте можно даже не заикаться. Но есть параметризованные алгоритмы: они решают NP-трудные задачи за время, зависящее, например, лишь линейно от объёма входных данных, а экспоненциально лишь от дополнительных параметров. Поэтому параметризованный алгоритм решает даже NP-трудную задачу эффективно в
приложениях, в которых параметр принимает малые значения.

Так что параметризованная теория сложности отвечает на вопрос, из-за чего именно вычислительная задача труднорешаема? Какие параметры, помимо объёма входных данных, влияют на её сложность? Может быть, они
в конкретном приложении малы и не так страшен чёрт, как его малюют?

2. Как доказывать эффективность алгоритмов редукции данных? Так как время работы алгоритмов зависит от объёма входных данных, желательно сводить исходные данные вычислительной задачи к данным меньшего объёма, не портя при этом оптимальное решение. К сожалению,
если не P=NP, то таких алгоритмов редукции данных нет для NP-трудных задач.

Однако тут тоже поможет параметризованный подход: можно уменьшить объём входных данных так, чтобы он был ограничен сверху функцией от параметров помимо объёма входных данных. Это позволяет строить алгоритмы редукции данных с гарантиями качества, то есть с доказуемыми оценками результативности, скорости, и качества решений.

Давайте оценку важности и влиятельности отдельных моих результатов оставим другим учёным: Наши результаты по маршрутизации транспорта и оптимизации беспроводных коммуникационных сетей получили премии на международных конференциях, о чем было написано в новостях тут и тут. Наши исследования по редукции данных посчитали достойными не только российские, но и немецкие фонды, о чём можно почитать тут.

Ещё можно посмотреть, какие из моих работ самые цитируемые. Выходит, большинство этих работ связаны с редукцией данных, задачами маршрутизации транспорта и задачами планирования. Так что с одной стороны мы работаем над задачами, которые довольно близки к приложениям. С другой стороны при решении этих задач мы регулярно открываем новые подходы к построению алгоритмов, которые переносятся на другие задачи оптимизации, и открываем новые свойства структур, к
которым эти алгоритмы применяются (например, свойства графов, матроидов, и гиперграфов).

Наши результаты скорее фундаментальные, так как мы рассматриваем базовые задачи, в то время как на практике часто возникают дополнительные ограничения искомых решений. Однако при решении, скажем, практических задач маршрутизации транспорта со сложными ограничениями всё равно в какой-то момент приходится решать те базовые задачи, которые рассматриваем мы. Подпроцедуры для их решения можем ускорить.

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

Я занимаюсь наукой с 2010г. За всё это время я без гранта сидел всего 7 месяцев. До мая 2015г я работал в Берлине, будучи исполнителем грантов Немецкого научно-исследовательского общества (DFG). С января 2016г я участвовал в проектах РНФ и руководил проектами РФФИ.

На данный момент я руковожу проектом по редукции данных, совместным с Берлинским техническим университетом, с поддержкой РФФИ и Немецкого
научно-исследовательского общества.

Мои исследования по параметризованным алгоритмам для оптимизации беспроводных коммуникационных сетей пока ещё поддерживаются стипендией Президента, но она закончится в ноябре.

У меня есть соавторы в Австралии, Германии, Израиле, Норвегии, США, Франции и Чехии. Также мы сейчас проводим исследования для одной зарубежной компании, но в силу соглашения о неразглашении не могу говорить о подробностях.

Умение строить эффективные алгоритмы пригодится в любых областях. А поиск этих алгоритмов часто порождает новые проблемы для исследований.

В нашей команде "параметризёров" помимо меня на данный момент один бакалавр, один аспирант, и один кандидат наук. До появления коронавируса мы регулярно обсуждали задачи в моём кабинете за чаем. Мой аспирант, кстати, на данный момент читает спецкурс о параметризованных алгоритмах.

Когда берёмся за исследования, то обычно с целью достичь результатов, тянущих на публикацию в международном журнале. Так что если главная цель у студента — лишь диплом в кармане, то это не к нам. Также я считаю студентов взрослыми людьми. Я никого заставлять работать не
буду. Если студент без этого не может работать, то это тоже не ко мне, ибо на положительный результат в таком случае можно не надеяться.

Студент должен уметь читать статьи на английском, так как практически вся литература о параметризованных алгоритмах исключительно на английском языке, да и мы сами пишем все статьи на английском, чтобы наши результаты были доступными широкому кругу читателей.

Важнее, чем знания, — желание работать. Ведь при желании всему можно научиться. Студент должен уметь сам организовываться, то есть, он сам должен следить за соблюдением сроков и формальностей.

На тему редукции данных. При этом у меня есть теоретические и экспериментальные темы. Задач, которые ещё не исследовались с точкой зрения редукции данных с гарантиями качества, довольно много, так что в этой области новые результаты получатся наверняка. В принципе студент может предложить задачу к исследованию.

Формальных требований у меня нет. Опыт показывает, что при желании всему можно научиться. Важно, чтобы желание было.