Algebraic Gems in
Theoretical Computer Science and Discrete Mathematics
CSC2429/ MAT1304
Fall 2021
Instructor: Shubhangi Saraf
Email: shubhangi.saraf@utoronto.ca
Timing: Monday 2 pm – 4 pm
Location: BA 2195 (and Zoom, link on quercus)
Office hours: by appointment
TA: Gregory Rosenthal
Course Syllabus/Information sheet
In the last few decades, algebraic methods have proven to be extremely powerful in several areas of computer science. Many of the recent and important advances in the field have relied on very simple properties of polynomials. In this course we will see many interesting and often surprising applications of linear algebra and polynomials to complexity theory, cryptography, combinatorics, and algorithm design. We will develop all the algebraic tools that we need along the way.
The main prerequisite is mathematical maturity. It might be helpful to have some familiarity with discrete math/algorithms and linear algebra. Students with an interest in discrete mathematics and/or theoretical computer science are welcome.
A tentative (and
partial) list of topics that we will cover:
· Applications of linear algebra
o Rank and dimension arguments, expander graphs
· Polynomials methods in combinatorics and discrete geometry
· Polynomials and error correcting codes
· Algebraic methods in complexity theory and cryptography
o Interactive proofs
o Polynomial identity testing
o Primality testing
o Circuit lower bounds
· Introduction to arithmetic circuits/arithmetic computation
Useful references/related material:
§ Linear Algebra Methods in Computer Science (By Laszlo Babai and Peter Frankl)
§ Thirty-three miniatures: Mathematical and Algorithmic Applications of Linear Algebra (By Jiri Matousek)
§ Linear algebra method: Blog post by Gowers
§ Course notes by Madhu Sudan (Algebra and computation)
§ survey on expanders by Hoory, Linial and Wigderson
Grading: 80% homework and 20% scribe notes and class participation. There is no exam.
Homework: There will be 3 or 4 problem sets over the semester