Algorithmic Methods Laboratory

• 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

Collaborations:

• 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