Arithmetic Circuit Complexity

Arithmetic Circuit Complexity

@VTU COE

0.0
(0) 0 Students
Download Brochure

What you will learn

  • none

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.

img
No Discussion Found

0.0

0 Reviews

5
0
4
0
3
0
2
0
1
0
Meet Your Instructor

Instructor
3.3 Rating
8558 Students
802 Courses
About Instructor

VTU is one of the largest Technological Universities in India with 24 years of Tradition of excellence in Engineering & Technical Education, Research and Innovations. It came into existence in the year 1998 to cater the needs of Indian industries for trained technical manpower with practical experience and sound theoretical knowledge.

video

Free

  • Course Duration
    28 h 4 m 44 s
  • Course Level
    Intermediate
  • Student Enrolled
    0
  • Language
    English
This Course Includes
  • 28 h 4 m 44 s Video Lectures
  • 2 Quizzes
  • 0 Assignments
  • 0 Downloadable Resources
  • Full Lifetime Access
  • Certificate of Completion