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:

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.