ACM India Winter School 3-12 Jan 2022, in association with CMI-NASI (Co-Organized by Chennai Mathematical Institute and IIT Madras) |
Algorithms & Lower Bounds
To Improve, Or Not To Improve, That's the Question!
ACM India Winter School 3-12 Jan 2022, in association with CMI-NASI (Co-Organized by Chennai Mathematical Institute and IIT Madras) |
What we know and what we don't! |
Our classical knowledge.
There are a handful of problems, like Sorting, for which we have achieved algorithms with the best possible running times; no (comparison-based) algorithm can sort n numbers in time better than O(n log n). On the other hand, for many 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 possible. 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.
Sure, we haven't made "significant" improvements, but this doesn't mean we have made no improvements at all! There has been very exciting research into 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. |
Advances in Algorithm Design |
Understanding the bottlenecks |
More insights into the hardness of problems.
Although we have not been able to exploit our belief, P!=NP, to understand the challenges involved in obtaining better algorithms for classical problems which are already solvable in polynomial time, this road does not lead to a dead-end. There has been a flurry of results that correlate the difficulties of designing better algorithms for various problems. A most 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 you can design an algorithm that solves the Longest Common Subsequence problem for two strings of length n in time O(n^{1.99}), then you will be able to beat the best known algorithm for Satisfiability, and will also disprove a well-believed conjecture about Satisfiability. In this course we will gain a deeper understanding on how these connections are established. |
Join us for the workshop!
(Application Deadline: 21 Nov.'21; selected students will need to pay a registration fee to confirm their participation) |