- Instructors : Neeraj Kayal and Chandan Saha Course number and Credits : E0 309 and 3:1 Lecture time : M,W 3:30-5 pm Venue : CSA 117
- Objective : The theme of the course in this semester is arithmetic circuit complexity. Arithmetic circuits are algebraic analogue of boolean circuits that naturally compute multivariate polynomials. The quest for a thorough understanding of the power and limitation of the model of arithmetic circuits (and its connection to boolean circuits) has lead researchers to several intriguing structural, lower bound and algorithmic results. These results have bolstered our knowledge by providing crucial insights into the nature of arithmetic circuits. Still, many of the fundamental questions/problems on arithmetic circuits have remained open till date.The aim of this course is to provide an introduction to this area of computational complexity theory. We plan to discuss several classical and contemporary results and learn about a wealth of mathematical (particularly, algebraic and combinatorial) techniques that form the heart of this subject.
- Grading policy :
- Paper presentations - 60%
- Scribing lecture notes - 40%
- Lectures (unedited notes scribed by students):