About this course

\( \def\DTIME{\mathsf{TIME}} \def\NTIME{\mathsf{NTIME}} \def\DSPACE{\mathsf{DSPACE}} \def\NSPACE{\mathsf{NSPACE}} \def\P{\mathsf{P}} \def\NP{\mathsf{NP}} \def\L{\mathsf{L}} \def\NL{\mathsf{NL}} \def\PSPACE{\mathsf{PSPACE}} \def\NPSPACE{\mathsf{NPSPACE}} \def\EXP{\mathsf{EXP}} \def\NEXP{\mathsf{NEXP}} \def\RP{\mathsf{RP}} \def\coRP{\mathsf{coRP}} \def\ZPP{\mathsf{ZPP}} \def\PP{\mathsf{PP}} \def\FP{\mathsf{FP}} \def\sharpP{\#\mathsf{P}} \def\BPP{\mathsf{BPP}} \def\AC{\mathsf{AC}} \def\NC{\mathsf{NC}} \def\SC{\mathsf{SC}} \)

This is an introductory course on algebra and computation. The main goal of this course is to demonstrate how algebra helps in algorithm design and do rigorous analysis of performance of these algorithms. The course will introduces the necessary basic algebra on groups, rings and fields. In this course, we will be looking at

• Groebner basis and its applications in robot motion planning
• Tensors and its connection to matrix multiplication algorithms
• Chinese remaindering and Hensel lifting
• Polynomial factorization algorithms
• Polynomial Identity Testing and its connections to derandomization and Circuit lower bounds
• Polynomial time algorithm for Primality testing (AKS algorithm).

The course syllabus can be found here

Links to similar courses

• Ramprasad Saptarishi's course page
• Madhu Sudan's course page, Offering from 2005, Offering from 2012
• Chandan Saha's course page
• Nitin Saxena's course page
• Manindra Agrawal's course page