This year, the school is devoted to modern trends in obtaining conditional hardness results for algorithmic problems. In the school we will learn about new developments in complexity theory which allow to derive tight bounds on the time required to solve computational problems.

The lectures will be taught by active researchers in these areas. Each of the tutorials will provide an introduction to the area and gradually bring to the current research frontiers. The primarily audience consists of PhD students interested in Algorithms. Master students, postdocs, young researchers and even faculty are also very welcome. The school continues the Recent Advances in Algorithms 2017 school (video recordings of all the lectures are available at the school webpage).

Recently, the field of computational complexity and algorithms has leveraged these assumptions to prove quantitative hardness results about a wide range of problems. Under these assumptions, we can prove lower bounds which match the running time of the best known algorithms for many problems. Although these lower are all conditional, they help to explain why making further algorithmic progress on these problems is difficult — and suggest that it might be impossible. Namely, any non-trivial algorithmic improvement would disprove a very well-studied hypothesis.

This course is devoted to studying the computational complexity of SAT and proving tight lower bounds on complexity of various problems. We will develop tools for working with SAT problems, and we will see how they allow us to turn many classical NP-hardness results into quantitative lower bounds. Then we will learn how to apply the developed techniques to prove lower bounds on "easy problems" which can actually be solved in polynomial time. We will also see how to amplify hardness: assuming only exponential hardness of SAT, we will prove even super-exponential lower bounds for graph homomorphism problems. Finally, we will encode Boolean formulas into geometric objects, to prove lower bounds on lattice problems.

The school is hosted by St. Petersburg Department of V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences which is located in the very center of St. Petersburg. St. Petersburg is particularly beautiful in the late spring — early summer, the white nights season. The city is surrounded by wonderful tsar parks and palaces; an excursion to one of them will be a social program of the school.

The school is organized by Fedor Fomin, Alexander S. Kulikov, Alexander Smal, and Monomax Company with the support by Computer Science Club, Ministry of Education and Science of the Russian Federation, JetBrains, and Yandex.