Skip to main content
Home

St. Petersburg Department
of Steklov Mathematical Institute
of Russian Academy of Sciences

27 Fontanka, St. Petersburg, Russia

Main menu

  • Institute structure
    • Administration
    • EIMI
    • Laboratories
    • Researchers
    • Academic council
    • Center of Research and Education
    • Publishing Department
    • Contacts
  • Activities
    • Conferences
    • Seminars
    • Dissertation Councils
    • Journal "Algebra and Analysis"
    • Journal "Zapiski Nauchnykh Seminarov POMI"
    • Preprints (partially in Russian)
    • Publications
  • Search
  • Resources
    • Video records
    • History of the Institute
    • Digital libraries (in Russian)
    • Links (in Russian)
    • Former Employees
    • Remembering Olga Ladyzhenskaya
    • PDMI Library

Fine-grained complexity

Максим Сергеевич Николаев

лаборатория прикладных вероятностных и алгоритмических методов
Position: 
Junior Researcher
Email: 
makc-nicko [at] yandex.ru
Homepage: 
https://orcid.org/0000-0003-4079-2885
Scientific Interests: 
Fine-grained complexity
приближенные алгоритмы
алгоритмы на строках

Публикации:

  1. Matveev A. S., Nikolaev M. S. Hybrid control for tracking environmental level sets by nonholonomic robots in maze-like environments //Nonlinear Analysis: Hybrid Systems. – 2021 – Т. 39 – С. 100982
  2. Nikolaev M. S. All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent //International Symposium on String Processing and Information Retrieval. – Springer, Cham, 2021 – С. 61-67.
  3. Matveev A. S., Nikolaev M. S. Reactive Autonomous Navigation of Nonholonomic Robots for Tracking Environmental Boundaries in Presence of Obstacles //2020 European Control Conference (ECC). – IEEE, 2020 – С. 1897-1902.
  4. Nikolaev M. S., Matveev A. S. Provable Reactive Navigation of Mobile Robots to a Moving Target in Unpredictable Dynamic Scenes //2019 IEEE 58th Conference on Decision and Control (CDC). – IEEE, 2019 – С. 220-225.
  5. Golovnev, A., Kulikov, A.S., Logunov, A., Mihajlin, I., Nikolaev, M. Collapsing Superstring Conjecture //Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). – Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019

Татьяна Сергеевна Белова

лаборатория прикладных вероятностных и алгоритмических методов
Position: 
Junior Researcher
Email: 
yukikomodo [at] gmail.com
Scientific Interests: 
Теория вычислительной сложности
Алгоритмы для NP-трудных задач
Параметризованные алгоритмы
Fine-grained complexity

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

2021 СПбГУ МКН “Современная Математика”

2019 СПбГУ МКН “Математика”

Публикации:

  1. T. Belova, A. Golovnev, A. S. Kulikov, I. Mihajlin, and D. Sharipov, “Polynomial formulations as a barrier for reduction-based hardness proofs”, in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2023, pp. 3245–3281.
  1. T. Belova and I. Bliznets, “Hardness of approximation for h-free edge modification problems: Towards a dichotomy”, in 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  1. T. Belova and I. Bliznets, “Algorithms for (n, 3)-maxsat and parameterization above the all-true assignment”, Theoretical Computer Science, vol. 803, pp. 222–233, 2020.
  1. T. Belova and I. Bliznets, “Upper and lower bounds for different parameterizations of (n, 3)-maxsat”, in International Conference on Combinatorial Optimization and Applications, Springer, 2018, pp. 299–313.

Логотип СПбРАН

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