Перейти к основному содержанию
Главная

Санкт-Петербургское отделение
Математического института
им. В.А.Стеклова РАН

наб. р. Фонтанки 27, Санкт-Петербург, 191023

Main menu

  • Новости
  • Структура института
    • Администрация
    • Институт им. Эйлера
    • Лаборатории
    • Научные сотрудники
    • Учёный совет
    • Научно-образовательный центр
    • Информационно-издательский сектор
    • Контакты
  • Ресурсы
    • Клуб сотрудников ПОМИ
    • Библиотека ПОМИ
    • Видеоматериалы
    • История института
    • Электронные библиотеки
    • Поступающим в аспирантуру
    • Ссылки
    • Научные сотрудники прошлых лет
    • Воспоминания об О.А. Ладыженской
  • Деятельность института
    • Конференции
    • Семинары
    • Диссертационные советы
    • Журнал "Алгебра и анализ"
    • Записки научных семинаров
    • Препринты
    • Публикации
    • Аспирантура
    • Противодействие коррупции
    • Антимонопольный комплаенс
    • Конкурс молодых ученых
  • Сотрудникам
    • Расписание аудиторий
    • Шаблоны документов бухгалтерии
    • Информация для сотрудников
    • Шаблоны документов отдела кадров
  • Вакансии
  • Поиск

теория сложности вычислений

Николай Николаевич Воробьев

лаборатория математической логики и дискретной математики
Должность: 
старший научный сотрудник
Учёная степень: 
кандидат ф.-м. наук
Email: 
vorobjov [at] pdmi.ras.ru
Научные интересы: 
вещественная алгебраическая и аналитическая геометрия
о-минимальные структуры
компьютерная алгебра
теория сложности вычислений

Краткая биография:

1979, ЛГУ (СПбГУ), факультет Прикладной математики - процессов упрaвления.

Список основных публикаций:

1. Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comp., 5, 1988, 37–64.  With D. Grigoriev

2. The complexity of deciding consistency of systems of polynomial in exponent

inequalities, J. Symbolic Comp., 13, 1992, 139–173.

3. The complexification and degree of a semialgebraic set, Mathematische

Zeitschrift, 239, 1, 2002, 131–142. With M.-F. Roy.

4. Complexity of computations with Pfaffian and Noetherian functions, in:

Normal Forms, Bifurcations and Finiteness Problems in Differential Equations,

NATO Science Series II, 137, Kluwer, 2004, 211–250. With A. Gabrielov.

5. Approximation of definable sets by compact families, and upper bounds on

homotopy and homology, J. London Math. Soc., 80, 2, 2009, 35–54. With A. Gabrielov.

 

https://people.bath.ac.uk/masnnv/Works22.pdf

Илья Николаевич Пономаренко

лаборатория математической логики и дискретной математики
Должность: 
ведущий научный сотрудник
Учёная степень: 
доктор ф.-м. наук
Email: 
inp [at] pdmi.ras.ru
Телефон: 
+7 (812) 310-73-17
Домашняя страница: 
http://www.pdmi.ras.ru/~inp/
Научные интересы: 
алгебраическая комбинаторика
группы перестановок
теория сложности вычислений

Краткая биография:

1979 - Ленинградский государственный университет, мат-мех, математик-преподаватель;

1990 - настоящее время, ПОМИ РАН.

Избранные публикации:

  1. I. Ponomarenko, The isomorphism problem for classes of graphs that are invariant with respect to contraction, Zapiski Nauchnykh Semin. LOMI, 174, 147–177 (1988).
  1. S. Evdokimov and I. Ponomarenko, Recognizing and isomorphism testing circulant graphs in polynomial time, Algebra Analiz, 15, No. 6, 1–34 (2003).
  1. S. Kiefer, P. Schweitzer, and I. Ponomarenko, The Weisfeiler-Leman dimension of planar graphs is at most 3, Journal of the ACM, 66, No. 6, Article 44 (2019).
  1. M. Muzychuk and I. Ponomarenko, Testing isomorphism of circulant objects in polynomial time, J. Combin. Theory, A169, 105128 (2020).
  1.  E. A. O’Brien, I. Ponomarenko, A. V. Vasil’ev, E. Vdovin The 3-closure of a solvable permutation group is solvable, 607, J. Algebra, no. 1, 618–637 (2022).

Дмитрий Михайлович Ицыксон

лаборатория математической логики и дискретной математики
Должность: 
ведущий научный сотрудник
Учёная степень: 
доктор ф.-м. наук
Email: 
dmitrits [at] pdmi.ras.ru
Научные интересы: 
теория сложности вычислений
теория сложности доказательств
сложность в среднем
нижние оценки
теория графов
экспандеры
математическая логика
алгоритмы

Образование:

2001 - 2006 Санкт-Петербургский государственный университет, математико-механический факультет, математическое обеспечение и администрирование информационных систем.

2006 - 2009 аспирантура ПОМИ РАН, защитил кандидатскую диссертацию «Сложность в среднем случае вероятностных вычислений с ограниченной ошибкой» в диссертационном совете при СПбГУ.

2022 защитил докторскую диссертацию «Нижние оценки и вопросы оптимальности для систем доказательств» в диссертационном совете при ПОМИ РАН.

Опыт работы:

ПОМИ РАН
2009 — 2011 м.н.с.

2011 — 2016 с.н.с.

2016 — 2017 ученый секретарь

2017 — наст. вр. в.н.с.

Санкт-Петербургский Академический университет РАН

2008 — 2010 преподаватель

2010 — 2019 доцент

СПбГУ

2018 — 2022 доцент

Награды:

Премия за лучшую статью на конференции CSR 2010;

Премия конкурса «Молодая математика России», 2018;

Премия за лучшую статью на конференции CSR 2019 (совместно с Л. Глинских).

Публикации:

  1. Dmitry Itsykson, Dmitry Sokolov, Resolution over linear equations modulo two. Ann. Pure Appl. Log. 171(1) (2020)
  2. Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov, On OBDD-based Algorithms and Proof Systems that Dynamically Change the order of Variables. J. Symb. Log. 85(2): 632-670 (2020)
  3. Edward A. Hirsch, Dmitry Itsykson, Ivan Monakhov, Alexander Smal, On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography. Theory Comput. Syst. 51(2): 179-195 (2012)
  4. Dmitry Itsykson, Structural complexity of AvgBPP. Ann. Pure Appl. Log. 162(3): 213-223 (2010)
  5. Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson, Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reason. 35(1-3): 51-72 (2005)

Список публикаций на DBLP https://dblp.org/pid/31/4688.html

  • Русский Русский
  • English English

Противодействие коррупции

COVID-19

QR код с информацией о коронавирусе

Для слабовидящих

Размер шрифта

– = +