Computational problems with ``efficient'' parallel algorithms are an important computational class in the theory and practice of algorithms. Many problems in linear algebra, like computing the determinant, can be solved by efficient parallel algorithms. Yet, a fundamental algorithm like Gaussian elimination does not have any efficient parallel algorithms. It is widely believed there efficiently solvable problems (like Gaussian elimination) that are inherently sequential, and they do not have any efficient parallel algorithms. This belief is captured by the famous question whether \(\textrm{P} \neq \textrm{NC}^1\)? This is one of the central problems in complexity theory.
Although it is believed that \(\textrm{P} \neq \textrm{NC}^1\), there are well known meta-mathematical barriers to proving such a result. In the '90s, an approach that surpasses all the known barriers was proposed by Karchmer, Raz, and Wigderson. They proposed a fundamental conjecture, known as the KRW conjecture, about the nature of computation in a model called Boolean formulas. Boolean formulas are a combinatorial model of computation closely modeling parallel computation and its tree structure forbids the reuse of computations. Karchmer Raz and Wigderson conjectured that for a certain composition of two Boolean functions \(f,g\), the optimal formula computing the composition has to be an inherently "sequential" composition of the optimal formulas computing \(f\) and \(g\). This conjecture if true would imply that \(\textrm{P} \neq \textrm{NC}^1\). An interesting feature of this conjecture is that, although the original conjecture is about Boolean formulas, due to a powerful bridge between communication complexity and circuit complexity established by Karchmer and Wigderson, the conjecture can equivalently be stated in the language of communication complexity. Almost all of the works on KRW conjecture exploit this connection and use insights and tools from communication complexity and information theory to make progress. Recently, there have been a lot of interesting developments in this research direction, resulting in breakthrough results and open problems. Yet, many interesting problems remain open and the evidence from recent research also points to the need for new tools and new ways of approaching these open problems.
The course has two main objectives. The first is to explain the larger goals of this research direction and to put the recent results in the context of these big picture goals. The second goal is to explore interesting open problems in this area and to make substantial progress in identifying and solving some of these open problems.
The course is aimed at graduate students and motivated undergraduate students. 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 specific research directions. Additionally, an understanding of communication complexity would be a big plus, but not mandatory.
As there are people who are attending this course but not crediting it, I am creating a mailing list for the course. I will post announcments and updates on the mailing list (like when lecture videos are uploaded to Youtube etc.).
There will be three assignments during the course. This will carry 60% of the grade. Apart from the assignments, there will be a final project which would account for the remaining 40%.
Tentatively : Mondays and Wedensdays 11:00-12:20 hrs
The lectures will start on Monday 28th September and end on Wednesday 9th December.
Password
Tentative : Friday 11:00-13:00
Password
Coming soon!!!
