There are many models and problems in complexity theory where the naivest solution to the problem is fairly close to the optimal solution. Such results are an extremely useful tool in proving lower bounds, as it is fairly is easy to analyze the complexity of naive solutions. More importantly, there has been a recent flurry of interesting developements in this research direction, resulting in a lot of interesting results and open problems.
The main theme of these result, as the title suggests, is to investigate models/problems where optimal solutions is asymptotically close to optimal solution. The course is divided into two parts.
Unsurprisingly there are models and problems where we formally do not if such a phenomenon is true. But if it were, it would imply fascinating lower bounds which are deemed beyond reach with other techniques. The first part focuses on a conjecture called KRW conjecture which concerns with analyzing optimal composition of Boolean formulas. Boolean formulas are a combinatorial model of computation closely modeling parallel computation and its tree structure forbids reuse of computations. It is widely believed that not all efficiently solvable problems can be solved also efficiently in parallel. But in Boolean formulas where no sub-computation can be reused, Karchmer Raz and Wigderson conjectured that under a certain composition of Boolean formulas the optimal has to be very "sequential" combination of the underlying formulas. If the conjecture is true it would be imply that \(P \not\in NC^1\), formally implying that not all efficiently solvable problems have efficient parallel solutions as well.
The second half of the course would focus on "lifting theorems". This line of work as the name suggests tries to lift lower bounds from a weaker model of computation to a much stronger model of computation. This is a very lucrative approach for proving lower bounds, as task of proving some taks is not efficiently solvable is much easier if we limit ourselfs to compuation models which are provably weaker than general algorithms. Thus the hard task is to
The course has two main objectives. The first is to explain the larger goal of these directions and to put the recent results in context of this big picture goals. The second goal is to explore interesting open problems in this area and to make substanatial progress on identifying and hopefully solving some of these open problems. To do so, we will explain the underlying philosphy of these approaches and the common tools and techniques used in obtaining these results.
The course plans to cover the state of the art in KRW conjecture and lifting theorems as much as possible. most lectures would present a key idea/result in the first half and in the second half we would have discussions around interesting open problems related to that result/idea.
The course will run every Tuesday from 13:30-16:30 in room AQ-5016. The first lecture will be on Tuesday, May 14th, 13:30. We will discuss administrative details in the first lectures, so please do come if you plan to attend the course. The course will run from May till August.
The course is aimed at graduate stduents and motivated undergrads. The only required prerequisite is an undergraduate level discrete math class so that you are familiar with the concept of formal proofs and basic mathematical structures like graphs, matrices etc. A course is in complexity theory is a plus as it would make it easier to understand some of the big goals of these directions and the drive for proivng better lower bounds. Additionaly an understanding of communication complexity would be a big plus, but not mandatory as we would cover most of the basics needed for understanding the tools and techniques used in these results in the initial lectures.
We will have office hours every week on Wednesdays 10:00-12:00 at TASC1 8201. The schedule for office hours is tentative and we can discuss and find out a different slot after the first lecture on Tuesday, May 14th.