Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Indian Institute of Technology Kanpur

Arithmetic Circuit Complexity

Indian Institute of Technology Kanpur and NPTEL via Swayam

Overview

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.

INTENDED AUDIENCE : Intersted students
PREREQUISITES : Preferable (but not necessary)-- Theory of Computation, Algorithms, Algebra
INDUSTRY SUPPORT : Cryptography, Coding theory, Symbolic Computing Software, Learning Software

Syllabus

COURSE LAYOUT Week -1 : Turing machines. Arithmetic circuits.
Week -2 : Newton's identity. Arithmetic branching program. Iterated matrix multiplication.
Week -3 : Arithmetic branching program vs. Determinant.
Week -4 : Circuit Depth Reduction.
Week -5 : Nontrivial reduction to constant-depth.
Week -6 : Width reduction.
Week -7 : Depth-3 over finite fields. Grigoriev-Karpinski measure.
Week -8 : Raz-Yehudayoff measure for multilinear depth-3.
Week -9 : Shifted partials of degree-restricted depth-4.
Week -10: Exponential lower bound for homogeneous depth-4.
Week -11: Polynomial Identity Testing (PIT) and exponential lower bounds are equivalent
Week -12: PIT for tiny depth-3 (or many other tiny models) suffices.

Taught by

Prof. Nitin Saxena

Related Courses

Reviews

Start your review of Arithmetic Circuit Complexity

Never Stop Learning!

Get personalized course recommendations, track subjects and courses with reminders, and more.

Sign up for free