The Laboratory of Algorithmic Methods was established at the St. Petersburg Department of the V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences (PDMI RAS) under the leadership of Professor Fedor Vladimirovich Fomin and with the support of the Ministry of Education and Science of the Russian Federation (Resolution 220, "megagrant").
Algorithmic solutions are applied in data processing underlying technological achievements such as Internet search engines, computer graphics, and bioinformatics. Laboratory staff develop new approaches to the design and analysis of algorithms and the study of computational complexity.
Project title: Construction of new efficient algorithms and proof of computational task difficulty
Goals and Objectives
Research Areas: Algorithms and complexity theory
Project Goal: Addressing fundamental questions of modern mathematics and computer science: studying the complexity of computational tasks
Practical significance of the research
Organizational and infrastructural transformations:
A non-profit research and education center has been established at the laboratory, hosting approximately twenty open courses on theoretical computer science and programming annually. Courses are taught by active scientists and practicing specialists. Video recordings and materials for all courses are publicly available on the Computer Science Club website.
Algorithmic solutions are applied in data processing underlying technological achievements such as Internet search engines, computer graphics, and bioinformatics. Laboratory staff develop new approaches to the design and analysis of algorithms and the study of computational complexity.
Project title: Construction of new efficient algorithms and proof of computational task difficulty
Goals and Objectives
Research Areas: Algorithms and complexity theory
Project Goal: Addressing fundamental questions of modern mathematics and computer science: studying the complexity of computational tasks
Practical significance of the research
Other results
- Several major international conferences on algorithms and complexity theory were organized: Third St. Petersburg Days of Logic and Computability 2015, 11th International Computer Science Symposium in Russia 2016, 15th International Symposium on Experimental Algorithms 2016, Journées sur les Arithmétiques Faibles 2017, and "Machine Learning and Algorithm Analysis in St. Petersburg 2017." The institute was visited by over 200 leading Russian and international specialists in the field of algorithm theory and computer science.
- Laboratory staff lead more than 10 grant-funded projects, including grants from the Russian Foundation for Basic Research, the Russian Science Foundation, the Council for Grants of the President of the Russian Federation, and other budgetary and commercial organizations.
- Annually, laboratory staff enter into commercial contracts for research and lecture courses with organizations such as Yandex, Samsung Research Center, Huawei, and others.
- Members of the research team regularly present reports at international symposia and conferences worldwide.
Scientific Results
- The lower bound on the size of Boolean circuits has been improved. This estimate not only sets a new world record for the size of such circuits but is also the first improvement (since 1984) of known lower bounds for one of the most fundamental models of computation.
- Fundamental problems regarding the computational complexity of graph and subgraph homomorphisms have been solved. Finding exact asymptotic complexity estimates for these problems was one of the central open questions in the field of exponential algorithms.
- The first parameterized algorithms were obtained for the shortest common superstring problem, which serves as a mathematical model for the genome assembly problem.
- A method was developed to prove the time hierarchy theorem for heuristic computations using the time hierarchy of distribution modeling. Time hierarchy theorems are the primary tool used to address a critical challenge in complexity theory: the separation of complexity classes.
Organizational and infrastructural transformations:
A non-profit research and education center has been established at the laboratory, hosting approximately twenty open courses on theoretical computer science and programming annually. Courses are taught by active scientists and practicing specialists. Video recordings and materials for all courses are publicly available on the Computer Science Club website.
Education and personnel retraining
- Three international student schools were held: the Student Research School on Algorithms and Complexity Theory in 2014 (80 participants), and two “Recent Advances in Algorithms” student schools in 2017 (70 participants) and 2018 (50 participants).
- Defenses: 1 doctoral dissertation (D.Sc.) and 4 candidate dissertations (Ph.D.) in the field of research.
- Annually, 1-2 new postgraduate students are admitted to the laboratory, undergoing training at the PDMI RAS under the supervision of research staff. Currently, the laboratory includes 5 postgraduate students and 7 Candidates of Sciences. Among the 5 Doctors of Sciences in the laboratory, one holds the title of Academician of the RAS and one is a Corresponding Member of the RAS.
- Twelve lecture courses on theoretical computer science were developed and delivered for undergraduate, graduate, and postgraduate programs, along with professional development courses for young specialists. Master's programs: "Analysis of Boolean Functions," "Efficient Algorithms," "Proof Complexity Theory," "Parameterized Algorithms," "Complexity-Theoretic Foundations of Cryptography," "Practical Programming and Data Analysis in Specialized Environments," "Information Theory." Undergraduate programs: "Mathematical Logic and Theory of Algorithms," "Theory of Algorithms," "Foundations of Discrete Mathematics and Mathematical Logic." Professional development programs: "Streaming Data Processing Algorithms," "Algorithms for NP-hard Problems." Courses were held at the RAS Scientific and Educational Center for Nanotechnology (Russia), St. Petersburg National Research Academic University of the RAS (Russia), Kazan Federal University (Russia), the Scientific and Educational Center at PDMI RAS, the Higher School of Economics (Russia), and St. Petersburg State University (Russia).
- Regular lecture courses by specialists in algorithms and theoretical computer science are organized to enhance the skills of the research team, as well as students, postgraduates, and employees of third-party organizations in Saint Petersburg. About 10 open lecture courses are held each semester at the PDMI RAS (video recordings of lectures are published on the Computer Science Club website).
Cooperation
- University of Bergen (Norway), Institute of Mathematical Sciences Chennai (India), University of Warsaw (Poland), University of California San Diego (USA), University of Turku (Finland), Courant Institute of Mathematical Sciences (USA): joint research and scientific publications.
- Institute of Mathematical Sciences Chennai (India), University of Bergen (Norway): new effective algorithms for hard problems on graphs and strings have been developed.
- University of Warsaw: new conditional lower bounds for graph embedding problems have been obtained.
- University of California, San Diego: two online specializations have been recorded on the international Coursera platform, with over two hundred thousand students from around the world currently enrolled.
Website: https://algo.pdmi.ras.ru/
Contact person: Fedor Vladimirovich Fomin
Address: 27 Fontanka River Emb.
Phone: +7 (812) 312-40-58
Email: admin@pdmi.ras.ru
Contact person: Fedor Vladimirovich Fomin
Address: 27 Fontanka River Emb.
Phone: +7 (812) 312-40-58
Email: admin@pdmi.ras.ru
Similar innovation and technology infrastructure facilities
