Aim of the School
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).
Courses
Due to health issues, Amir will not be able to attend the school.
The Satisfiability problem (SAT) is a canonical example of an easy to state but hard to solve problem. SAT is the problem of determining whether a given Boolean formula has a satisfying assignment. Despite decades of efforts, we still don't know algorithms which solve SAT significantly faster than the brute force search. Impagliazzo and Paturi (1999) conjectured that SAT cannot be solved in sub-exponential time. And a stronger version of their hypothesis asserts that SAT cannot be solved exponentially faster than brute force.
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.
Ivan Mihajlin (UCSD), Non-equivalence of Hardness Assumptions
Recent results in fine-grained complexity give us an understanding of how the complexity of different problems relates one to another. This way we can talk about the hardness of a problem conditioned on the hardness of another problem. The primary tool to prove such hardness results is to provide reductions between problems. The objective of this course is to understand limitations of this tool. We will try to answer the following type of questions: Is there a reduction between two problems? We will go over several methods to justify the negative answer to this sort of questions.
Venue
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.
