Fine Grained Algorithms & Complexity (CS6100)
Important Links
Teaching Group
An Introductory Note
Our classical knowledge. There are a handful of problems, like Sorting, for which we have achieved algorithms with the best possible running time; no comparison based algorithm can sort n numbers in time better than O(n log n). For many other problems like Graph Diameter, All-pairs Shortest Paths, Boolean Matrix Multiplication, and 3-SUM, we have neither seen "significantly improved" algorithms, nor results like that for sorting, which guarantee that the existing algorithms are the best. The Million Dollar P != NP conjecture does not give us insights into why we are unable to obtain better algorithms for these problems. This is not very surprising: the conjecture only distinguishes between problems that admit polynomial time algorithms and those that do not admit such an algorithm.
Enhancing our algorithmic toolkit. Although we haven't made "significant" improvements, but this doesn't mean we have made no improvements at all! There has been very exciting research in obtaining better algorithms. These use techniques ranging from simple ones such as look-ups to very innovative techniques employing the Fast Fourier Transformation and the Polynomial Method. These give us better algorithms than the very well-known classical algorithms for various problems which we come across in a first course in Algorithm Design and Analysis. We will learn these amazing techniques to build better algorithms for several of our favourite polynomial time solvable problems.
More insights into the hardness of problems. Though we have not been able to exploit our belief, P!=NP, to understand the challenges involved in obtaining better algorithms for classical polynomial time solvable problems, this road does not lead to a dead-end. There have been a flurry of results that correlate the difficulties of designing better algorithms for various problems. One of the very interesting connection is the one between a problem in P and a problem that is arguably our favourite NP-complete problem, viz., Satisfiability. It turns out that if we can design an algorithm that solves the Longest Common Subsequence problem (for two strings) of length n in time O(n^{1.99}), then we will be able to beat the best known algorithm for Satisfiability, and this will disprove a well-believed conjecture about Satisfiability. In this course we will gain a deeper understanding on how these connections are established.
Contents of the Course
We will closely follows the courses taught by Karl Bringmann and Virginia Vassilevska Williams on this subject. Some of the concrete topics that we intend to cover in this course are:
Tune in for fun stuff!
Relevant References and Additional Readings for the Lectures
Some Practical Information
Tentative Timings: Monday 10:00-10:50, Tuesday 09:00-09:50, Wednesday 08:00-08:50, and Friday 12:00-12:50.
Evaluation (tentative) and Timelines:
Attendance requirement for the course will be as mandated by the institute. In case a student needs to avail any waiver based on institute norms (if any) that allows students satisfying certain criterion to watch the videos of the lectures offline, then you are required to take permission regarding the same from the instructor. The last component is added in the evaluation with the hope to enhance learning, particularly in the online setting. In case you face connectivity issues, then we will make alternative arrangements to facilitate for the last component of the evaluation, in which case it is required that student communicates the issue via email to me, as and when necessary.
The mode of final presentation will be decided later, based on the situation.
- Class: meet.google.com/zrr-yrff-yat
Teaching Group
- Instructor: Akanksha Agrawal
- Teaching Assistant: TBD
An Introductory Note
Our classical knowledge. There are a handful of problems, like Sorting, for which we have achieved algorithms with the best possible running time; no comparison based algorithm can sort n numbers in time better than O(n log n). For many other problems like Graph Diameter, All-pairs Shortest Paths, Boolean Matrix Multiplication, and 3-SUM, we have neither seen "significantly improved" algorithms, nor results like that for sorting, which guarantee that the existing algorithms are the best. The Million Dollar P != NP conjecture does not give us insights into why we are unable to obtain better algorithms for these problems. This is not very surprising: the conjecture only distinguishes between problems that admit polynomial time algorithms and those that do not admit such an algorithm.
Enhancing our algorithmic toolkit. Although we haven't made "significant" improvements, but this doesn't mean we have made no improvements at all! There has been very exciting research in obtaining better algorithms. These use techniques ranging from simple ones such as look-ups to very innovative techniques employing the Fast Fourier Transformation and the Polynomial Method. These give us better algorithms than the very well-known classical algorithms for various problems which we come across in a first course in Algorithm Design and Analysis. We will learn these amazing techniques to build better algorithms for several of our favourite polynomial time solvable problems.
More insights into the hardness of problems. Though we have not been able to exploit our belief, P!=NP, to understand the challenges involved in obtaining better algorithms for classical polynomial time solvable problems, this road does not lead to a dead-end. There have been a flurry of results that correlate the difficulties of designing better algorithms for various problems. One of the very interesting connection is the one between a problem in P and a problem that is arguably our favourite NP-complete problem, viz., Satisfiability. It turns out that if we can design an algorithm that solves the Longest Common Subsequence problem (for two strings) of length n in time O(n^{1.99}), then we will be able to beat the best known algorithm for Satisfiability, and this will disprove a well-believed conjecture about Satisfiability. In this course we will gain a deeper understanding on how these connections are established.
Contents of the Course
We will closely follows the courses taught by Karl Bringmann and Virginia Vassilevska Williams on this subject. Some of the concrete topics that we intend to cover in this course are:
- A quick recap of the required basics
- An introduction to (un)conditional lower bounds and a few such bounds
- Going by our arguably favourite Indian way of fixing problems, the jugaad, reductions and more...
- Simple algorithmic improvements using the good old dynamic programming and lookups.
- Some basics of Fast Fourier Transformation and their applications
- The polynomial method and its applications
- Linear Decision Trees
- Bottlenecks to faster algorithms, famous conjectures from P and beyond
- Relating hardness of different problems
Tune in for fun stuff!
Relevant References and Additional Readings for the Lectures
- Lecture 1: Introductory lecture.
- Lecture 2-3: See Chapter 3 of the textbook, Introduction to Algorithms, by Cormen , Leiserson, Rivest and Stein.
- Lecture 4-5: See Chapter 8 of the textbook, Algorithm Design, by Klienberg and Tardos.
- Lecture 6-7: See Chapter 13 of the textbook, Algorithm Design, by Klienberg and Tardos.
- Lecture 8-12: You can check the following slides and notes by Karl Bringmann: pdf1, pdf2, pdf3, pdf4. Also check the proof of Theorem 8 and 9 (and relevant definitions) from this paper.
- Lecture 13-14: Notes by Karl Bringmann: pdf1, Section 4.5, Section 22.4-22.5 of the textbook, Introduction to Algorithms, Cormen et al.
- APSP and its relatives.
- Polynomial Method for OV and some basics.
- Polynomial Method for APSP.
- Improved 3-SUM algorithms.
Some Practical Information
Tentative Timings: Monday 10:00-10:50, Tuesday 09:00-09:50, Wednesday 08:00-08:50, and Friday 12:00-12:50.
Evaluation (tentative) and Timelines:
- (45%) Assignments (roughly 3-4).
- (50%) Learning Project: Each student individually, or along with a fellow classmate will be required to select a research paper (by emailing me, latest by 10/02/22) from the list that will be shared in the beginning of the course. The papers will be allocated on a first-come-first-serve basis. After the allotment of the paper, your job is to read and understand the research article with complete details, and to submit the following report based on the paper assigned to you:
- (17/02/22) Short report (in latex, less than 2 pages) that summarises the problem(s) studied in the paper, a summary of prior works done on this and related problems, new results obtained in the paper, and techniques used for obtaining the results. Furthermore, state which is your favourite result from the paper and tell us why you like this result.
- (17/03/22) Progress Report (in latex, less than 3 pages). Present an overview of the sections/results that you covered from the paper, and write a sketch of how these results are obtained.
- In class-presentation over Google Meet, which will tentatively happen in April (the exact dates will be decided based on the number of attendees).
- (28/04/22) Final Report (in latex, at least 4 pages).
- (5%) Class participations.
Attendance requirement for the course will be as mandated by the institute. In case a student needs to avail any waiver based on institute norms (if any) that allows students satisfying certain criterion to watch the videos of the lectures offline, then you are required to take permission regarding the same from the instructor. The last component is added in the evaluation with the hope to enhance learning, particularly in the online setting. In case you face connectivity issues, then we will make alternative arrangements to facilitate for the last component of the evaluation, in which case it is required that student communicates the issue via email to me, as and when necessary.
The mode of final presentation will be decided later, based on the situation.
