Главная страница
Главная страница
Диссертационные советы
Текущая работа диссоветов
Архив
Справочная информация по вопросам научной аттестации
Ф.И.О. Сироткин Дмитрий Валерьевич
Диссертация Кандидатская диссертация на тему: Исследование вычислительной сложности задач о независимом множестве и о вершинной k-раскраске в некоторых классах графов (1.87 Мб, загрузить)
Диссертационный совет Д 212.166.20
Научная специальность 01.01.09 - Дискретная математика и математическая кибернетика (физико-математические науки)
Дата защиты 23.01.2020
Статус принята к защите
Автореферат Загрузить
Объявление на сайте ВАК https://vak.minobrnauki.gov.ru/advert/100045466
Ведущая организация Федеральное государственное бюджетное образовательное учреждение высшего образования «Ярославский государственный университет им. П.Г. Демидова»

Адрес: 150003, Ярославль, Советская ул., 14

Организации, где выполнялась диссертация Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики»
Место работы Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики», Лаборатория алгоритмов и технологий анализа сетевых структур
Научный руководитель Малышев Дмитрий Сергеевич, доктор физико-математических наук, доцент, «Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского», институт ИТММ, кафедра алгебры, геометрии и дискретной математики (отзыв)
Оппоненты
  1. Жуковский Максим Евгеньевич, доктор физико-математических наук (01.01.09), доцент, доцент кафедры дискретной математики, федеральное государственное автономное образовательное учреждение высшего образования «Московский физико-технический институт (национальный исследовательский университет)».

    Наименования отрасли науки, научной специальности, по которым оппонентом защищена диссертация:
    01.01.09 - дискретная математика и математическая кибернетика

    Список основных публикаций официального оппонента по теме диссертации в рецензируемых научных изданиях за последние 5 лет:
    1. Д. И. Дмитриев, М. Е. Жуковский, “О связи двух задач теории графов с гипотезами Рамануджана и Самуэльса”, Успехи мат. наук, 73:4 (442) (2018), 173–174.
    2. А. В. Гасников, П. Е. Двуреченский, М. Е. Жуковский, С. В. Ким, С. С. Плаунов, Д. А. Смирнов, Ф. А. Носков, “Вокруг степенного закона распределения компонент вектора PageRank. Часть 2. Модель Бакли–Остгуса, проверка закона для этой модели и устройство реальных поисковых систем”, Сиб. журн. вычисл. матем., 21:1 (2018), 23-45.
    3. А. В. Буркин, М. Е. Жуковский, “Малые подграфы и их расширения в случайном дистанционном графе”, Матем. сб., 209:2 (2018), 22–46.
    4. М. Е. Жуковский, Л. Б. Островский, “Свойства первого порядка ограниченной кванторной глубины сильно разреженных случайных графов”, Изв. РАН. Сер. матем., 81:6 (2017), 100–113
    5. М. Е. Жуковский, “Перемены кванторов в формулах первого порядка с бесконечным спектром”, Пробл. передачи информ., 53:4 (2017), 95–108.
    6. М. Е. Жуковский, А. Д. Матушкин, “Универсальный k-закон нуля или единицы”, Матем. заметки, 99:4 (2016), 511–525.
    7. М. Е. Жуковский, А. Е. Медведева, “Когда не выполнен k-закон нуля или единицы?”, Матем. заметки, 99:3 (2016), 342–349.
    8. М. Е. Жуковский, “О 4-законе нуля или единицы для случайного графа Эрдеша–Реньи”, Матем. заметки, 97:2 (2015), 203–216.
    9. М. Е. Жуковский, “Спектры формул первого порядка малой кванторной глубины”, Успехи мат. наук, 70:6(426) (2015), 209–210.
    10. М. Е. Жуковский, А. М. Райгородский, “Случайные графы: модели и предельные характеристики”, Успехи мат. наук, 70:1(421) (2015), 35–88

  2. Куликов Александр Сергеевич, доктор физико-математических наук (01.01.06), заведующий лабораторией прикладных вероятностных и алгоритмических методов, федеральное государственное бюджетное учреждение науки «Санкт-Петербургское отделение математического института им. В.А. Стеклова РАН»

    Наименования отрасли науки, научной специальности, по которым оппонентом защищена диссертация:
    01.01.06 - математическая логика, алгебра и теория чисел

    Список основных публикаций официального оппонента по теме диссертации в рецензируемых научных изданиях за последние 5 лет:
    1. A.S. Kulikov, V.V. Podolskii. Computing majority by constant depth majority circuits with low fan-in gates. Theory of Computing Systems 63 (5), (2019) 956-986.
    2. A. Golovnev, E.A. Hirsch, A. Knop, A.S. Kulikov. On the limits of gate elimination. Journal of Computer and System Sciences 96, (2018) 107-119.
    3. A. Golovnev, A.S. Kulikov, A.V. Smal, S. Tamaki. Gate elimination: circuit size lower bounds and# SAT upper bounds. Theoretical Computer Science 719, (2018) 46-63.
    4. I. Bliznets, F.V. Fomin, P.A. Golovach, N. Karpov, A.S. Kulikov, S. Saurabh. Parameterized complexity of superstring problems. Algorithmica 79 (3), (2017) 798-813.
    5. M. Cygan, F.V. Fomin, A. Golovnev, A.S. Kulikov, I. Mihajlin, J. Pachocki, A. Socała. Tight lower bounds on graph embedding problems. Journal of the ACM (JACM) 64 (3), (2017) 18 pages.
    6. F.V. Fomin, P.A. Golovach, N. Karpov, A.S. Kulikov. Parameterized complexity of secluded connectivity problems. Theory of Computing Systems 61 (3), (2016) 795-819.
    7. A. Golovnev, A.S. Kulikov, I. Mihajlin. Families with infants: speeding up algorithms for NP-hard problems using FFT. ACM Transactions on Algorithms (TALG) 12 (3), (2016) 35.
    8. E. Demenkov, A.S. Kulikov, O. Melanich, I. Mihajlin. New lower bounds on circuit size of multi-output functions. Theory of Computing Systems 56 (4), (2015) 630-642.

История

14.10.2019 - Текст диссертации размещён в сети Интернет

31.10.2019 - Диссертация принята к защите (протокол № 13/19 от 31.10.2019)

принята к защите