We use cookies.
By using the site, you agree to our Privacy Policy.

Contract number
Time span of the project

As of 30.01.2020

Number of staff members
scientific publications
General information

Name of the project: Building new efficient algorithms and proving compleity of quantitative tasks

Strategy for Scientific and Technological Development Priority Level: а

Goals and objectives

Research directions: Algorithms and complexity theory

Project objective: Solving fundamental problems of modern mathematics and informatics: study of complexity of computatios

The practical value of the study

  • A new lower bound on circuit size of explicitly defined Boolean function was proved. This lower bound not only sets a new world record for the sizes of such circuits, but also is the first such improvement since 1984 for one of the most fundamental computational models
  • The first parameterized algorithms for the superstring problem have been found. This problem is the mathematical model of the genome assembly problem.
  • We have solved fundamental problems of graph and subraphs homomorphism computation complexities. Finding precise asymptotic complexity estimates for these tasks was on of central unresolved problems in exponential algorithms.
  • A method that allows to prove time hierarchy theorems for heuristic computations, based on time hierarchies for sampling distributions, has been developed. Time hierarchy theorems are the main tool that is used for the separation of complexity classes; the latter is the most important problem in complexity theory
  • Every year 1 or 2 new postgraduate students from the St. Petersburg Department of the Institute of Mathematics come to work at the Laboratory under the auspices of our scientific staff. There are currently 5 postgraduates and 7 candidates of sciences in the Laboratory. Among the 5 doctors of sciences of our Laboratory, one is a corresponding member of the Russian Academy of Sciences.

Education and career development:

  • We have conducted 3 international student schools: Student scientific school on algorithms and complexity theory in 2014 (80 participants), two student schools “Recent Advances in Algorithms” in 2017 (70 participants) and 2018 (50 participants).
  • 1 doctoral dissertation, 4 candidate dissertations in our research domain have been defended.
  • We have developed and taught 12 lecture courses in theoretical informatics for bachelors, masters and postgraduates, professional training courses for young professional. Master programs: «Analysis of boolean functions», «Efficient algorithms», «Theories of proving complexity», «Parametrized algorithms», «Theory and complexity basics of cryptography», «Practical programming and data analysis in specialized environment», «Information theory». Bachelor programs: «Mathematical logic and algoithm theory» «Algorithm theory», «Basics of discrete mathematics and mathematical logic». Professional training courses: «Algorithms for data flow processing», «Algorithms for NP- problems». The courses have been read of Research and eduaction center of nanotechnologies of the Russian Academy of Sciences (Russia), Saint Petersburg Academic University of the Russian Academy of Sciences (Russia), Kazan Federal University (Russia), Scientific and Educational Center of the Saint Petersburg Department of the Steklov Institute of Mathematics of the Russian Academy of Sciences, Higher School Economics (Russia), and St. Petersburg State University (Russia)

Organizational and structural changes:

  • Our Laboratory has organized regular lecture courses in algorithms and theoretical informatics to train scientific staff, undergraduate and postgraduate students and employees of St. Petersburg foundations. About 10 open lecture courses are conducted every year at the Saint Petersburg Department of the Steklov Institute of Mathematics of the Russian Academy of Sciences (videotapes of lectures are posted at the Computer Science Club site).

Other results:

  • We have organized several major international conferences and algorithms and complexity theory: 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, «Machine learining and algorythis analysis in St. Petersburg 2017». Over 200 leading Russian and foreign professionals in algorithms theory and computer scientists have come to the Insitute.
  • The Laboratory's employees lead over 10 projects, receive grant including grants from the Russian Foundation for Fundamental Research, Russian Sciencitic Foundations, Grant Council of the President of Russia and other budgetary and commercial organizations
  • Every year employees of the Laboratory sign commercial contracts to conduct research and prepare lecture courses with Yandex, Samsung Research Center, Huawei and others.
  • Members of scientific staff regularly deliver speeches at international symposiums and conferencess all across the world


  • 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 publication
  • Institute of Chennai (India), University of Bergen (Norway): we have developed new efficient algorithms for complex problems in graphs and string
  • University of Warsaw (Poland): we have obtained new lower bound for te problem of graph inclusion
  • University of California San Diego: two online specializations have been produces for the Coursera education platform, over 200 000 students are currently enrolled into those courses all around the world

Hide Show full
Cygan M., Fomin F.V., Golovnev A., Kulikov A.S., Mihajlin I., Pachocki J., Socala A.
Tight Lower Bounds on Graph Embedding Problems. J. ACM 64(3), 18:1–18:22 (2017).
Kogan K., Nikolenko S.I., Eugster P., Shalimov A., Rottenstreich O.
Efficient FIB Representations on Distributed Platforms. IEEE Transactions on Networking. 25(6): 3309–3322 (2017).
Golovnev A., Kulikov A.S., Mihajlin I.
Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT. ACM Trans. Algorithms 12(3): 35:1–35:17 (2016).
Find M.G., Golovnev A., Hirsch E.A., Kulikov A.S.
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. IEEE 57th Annual Symposium on Foundations of Computer Science FOCS 89–98 (2016).
Abramovskaya T.V., Fomin F.V., Golovach P.A., Pilipczuk M.
How to hunt an invisible rabbit on a graph. European Journal of Combinatorics 52, Part A: 12–26 (2016).
Other laboratories and scientists
Hosting organization
Field of studies
Invited researcher
Time span of the project
Laboratory «Hybrid modeling and optimization methods in complex systems»

Siberian federal University - (SibFU)

Computer and information sciences


Stanimirović Predrag Stefan



Laboratory «Research of ultra-low-latency network technologies with ultra-high density based on the extensive use of artificial intelligence for 6G networks»

The Bonch-Bruevich Saint Petersburg State University of Telecommunications

Computer and information sciences

St. Petersburg

Abd El-Latif Ahmed Abdelrahim



Laboratory for Non-linear and Microwave Photonics

Ulyanovsk State University - (USU)

Computer and information sciences


Taylor James Roy

United Kingdom, Ireland