Instructor : Mrinal Kumar and Sundar Vishwanathan
Email : first name AT cse DOT iitb DOT ac DOT in
Time : Wed/Fri 11:05 am-12:30 pm
Location : CC101
Office hours : Wednesday, 2:30 pm-3:30pm in 308, New CS Building
Algebraic ideas play a crucial role in many applications in Theoretical Computer Science and Discrete Math. We will see some of these ideas and their applications to problems in Algorithm Design, Coding Theory, Combinatorics, Discrete Geometry, Discrete Math and Number Theory. A tentative list of topics can be found here.
The semester was cut short at this point due to the pandemic. Below is a tentative list of some of the things we might have seen in the remaining lectures under less abnormal circumstances, and some references to them.
Refs: More than one proof of the standard polynomial identity lemma can be found on Anurag Bishnoi's blog here. For the multiplicity version of the lemma and its application to improved bounds on Kakeya sets, see Chapters 1 and 4 of Shubhangi Saraf's PhD thesis here.
Refs: For average case hardness of permanent, notes by Yuval Filmus here. Combinatorial designs (also referred to as Nisan-Wigderson designs in CS literature) can be found in the lecture notes of a random Complexity Theory class on the internet with high probability. For instances see the beginning of Section 2 for a definition of designs and sub-section 2.1 for their construction in these notes from a course by Kristoffer Hansen.
Refs: A sketch of a fast parallel algebraic algorithm for the determinant can be found in the notes of Nitin Saxena here. Given a fast parallel algorithm for the determinant, it is not hard to use it to get a fast (but randomized) parallel algorithm for bipartite perfect matching. A nice overview of this problem, along with some very recent work can be found in this article by Stephen Fenner, Rohit Gurjar and Thomas Thierauff.
Refs: See section 2 of these notes from a course by Swastik Kopparty. For some of the notations, you might have to look at an earlier lecture, or do a naive google search. This theorem is also highly likely to be there in the notes of any standard course on Computational Complexity.
Refs: See the original paper of Alman and Williams.
Refs: The algorithms for primality testing can be found in these notes (here and here by Swastik Kopparty.) Also see section 4.1 here. The original papers of Agrawal and Biswas and that of Agrawal, Kayal and Saxena are also quite readable (and highly recommended). For the second part of the lecture, we intended to look at some results on rational approximations of irrational numbers. An exposition to these can be found in these notes (lec25, lec26 and lec27) from a course on the polynomial menthod taught by Larry Guth.