Course Name: Arithmetic Circuit Complexity

Course abstract

In this course we will study computation by primarily algebraic models, and use, or in many cases extend, the related tools that mathematics provides. We will start with some positive examples-- fast polynomial multiplication, matrix multiplication, determinant, matching, linear/algebraic independence, etc. The related tools are FFT (fast fourier transform), tensor rank, Newton's identity, ABP (algebraic branching program), PIT (polynomial identity testing), Wronskian, Jacobian, etc. One surprising result here is that certain problems for general circuits reduce to depth-3 circuits. Furthermore, the algorithmic question of PIT is related to proving circuit lower bounds. We then move on to proofs, or attempts to prove, that certain problems are hard and impossible to express as a small circuit (i.e. hard to solve in real life too). One such problem is Permanent. We study the hardness against restricted models-- diagonal circuits, homogeneous depth-3, homogeneous depth-4, noncommutative formulas, multilinear depth-3, multilinear formulas, read-once ABP, etc. The partial derivatives, and the related spaces, of a circuit will be a key tool in these proofs. The holy grail here is the VP/VNP question. Depending on time and interest, other advanced topics could be included. One such growing area is-- GCT (geometric complexity theory) approach to the P/NP question.


Course Instructor

Media Object

Prof. Nitin Saxena

Prof. Nitin Saxena, Professor at the Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, has been awarded the 2018 Shanti Swarup Bhatnagar Prize for his work in Algebraic Complexity Theory. One of the youngest awardees, Prof. Saxena’s research interests include Computational Complexity and Algebraic Geometry. The Shanti Swarup Bhatnagar Prize, named after the founder of the Council of Scientific and Industrial Research (CSIR), is awarded for outstanding and notable research in the field of science and engineering. It includes Rs 5,00,000 prize money, a citation plaque and a fellowship till the age of 65. Prof. Saxena’s work deals with a topic in Mathematics called Polynomial Identity Testing and certain mathematical objects called ‘algebraic circuits’. Some mathematical problems, like solving a sudoku puzzle, could have fast and accurate approaches. However, a problem like finding all possible ways to solve a sudoku puzzle of any size becomes an extremely complex one. Such complex problems can be represented by polynomials—expressions that involve variables and operations like addition, subtraction, multiplication and exponents. Polynomial Identity Testing explores if two polynomials, involving multiple variables, are equal. Algebraic methods help in determining how complicated it would be to solve this. Theoretical research in the area of Polynomial Identity Testing could potentially help in cryptography, error-correction, optimisation of algorithms and systems, and machine learning.
More info

Teaching Assistant(s)

Prateek Dwivedi

P.hD

Pranjal Dutta

P.hD

 Course Duration : Jan-Apr 2020

  View Course

 Syllabus

 Enrollment : 18-Nov-2019 to 03-Feb-2020

 Exam registration : 16-Dec-2019 to 20-Mar-2020

 Exam Date : 25-Apr-2020

Enrolled

633

Registered

Certificate Eligible

Will be announced

Certified Category Count

Gold

Will be announced

Elite

Will be announced

Successfully completed

Will be announced

Participation

Will be announced

Success

Elite

Gold





Legend

Final Score Calculation Logic

Toppers list will be updated shortly....!

Enrollment Statistics

Total Enrollment: 633

Registration Statistics

Total Registration : 3

Assignment Statistics




Assignment Score

Graph will be updated shortly...!

Score Distribution Graph - Legend

Assignment Score: Distribution of average scores garnered by students per assignment.
Exam Score : Distribution of the final exam score of students.
Final Score : Distribution of the combined score of assignments and final exam, based on the score logic.