Course Description
Algebra plays an important role in both finding algorithms and understanding the limitations of computation. This course will focus on some of the fundamental algebraic concepts that arise in computation and the algebraic algorithms that have applications in the real life. The course will cover the problems of fast integer (or polynomial) multiplication (or factoring), fast matrix multiplication, primality testing, computing discrete logarithm, polynomial identity testing, list-decoding, cryptography, etc. The course intends to introduce both basic concepts and practical applications.
Course Audience
Anyone with interest in Algebra/Complexity is welcome in this course.
Weekly meeting:
Wednesday 12:00 pm
Please click here to join the zoom meeting: https://iitk-ac-in.zoom.us/j/91872464444?pwd=c1RyVlRTVHNVQU5Ld01ialFKN052Zz09
Meeting Id: 91872464444
Meeting Password: EVg964XC
Outcomes of this Course
TOPICS (TENTATIVE).
- Basic algebra results, algorithms
- Polynomial multiplication
- Integer multiplication
- Matrix multiplication
- Polynomial factoring -- over finite fields
- Reed-Solomon codes and list decoding
- Blackbox factoring
- Polynomial factoring -- over rationals
- Lattices, NTRU cryptosystem
- Primality testing
- Integer factoring
- Elliptic curves
- Discrete logarithm