Winter School on Algorithms and Lower Bounds: To Improve, or Not to Improve, That’s the Question!

In association with CMI-NASI

** Selected students for Winter Schools 2022 have been informed individually by email about the next steps. **

Dates: 3 to 12 January 2022

Academic coordinators:

Akanksha Agrawal (IITM) [email protected]
G. Philip (CMI) [email protected]

Hosted by Chennai Mathematical Institute and Indian Institute of Technology Madras

Platform: Zoom (for lectures); Gather (for tutorials and breakouts)

Overview of the School:
In this course we revisit some “easy” polynomial-time solvable problems. We explore some recent developments that give us algorithmic improvements using new techniques (like FFT-based methods and the polynomial method), and better lower bounds based on some well-known conjectures other than P ≠ NP. We will begin with a quick recap of the basics of algorithm design, and then move on to advanced algorithmics.

List of subtopics:

Recap on basics of algorithms
Simple algorithmic improvements using look-ups, and their applications
Improvements based on Fast Fourier Transformation
The Polynomial Method and its applications
Linear Decision Trees
Bottlenecks to faster algorithms, famous conjectures from P and beyond
Relating difficulties among problems in P and beyond

Proposed list of speakers (with affiliations):

Akanksha Agrawal (Indian Institute of Technology Madras, Chennai)
G. Philip (Chennai Mathematical Institute)
Saket Saurabh (Institute of Mathematical Sciences, Chennai)
Venkatesh Raman (Institute of Mathematical Sciences, Chennai)

Background/prior courses recommended (full semester courses on the following subjects):

Algorithm Design and Analysis
Discrete Mathematics

(Or courses equivalent to the above) Also, it is expected that attendees have the mathematical maturity to follow proofs.