The class will focus on two key themes, which have proven to be extremely powerful in several areas of computer science. The first is algebraic techniques. We will see many interesting and often surprising applications of linear algebra and polynomials in coding theory, cryptography, combinatorics, and algorithm design. We will develop all the algebraic tools that we need along the way. The second is the use of randomness in computation. We will explore both the power of randomized algorithms, and also of ways to eliminate or reduce randomness in algorithms. We will see applications in graph theory, data structures and complexity theory.
No specific background is necessary. However, it might be helpful to have some familiarity with discrete math/algorithms and linear algebra. The only real prerequisite is some mathematical maturity. Students with an interest in discrete mathematics and/or theoretical computer science are welcome.
Topics
Mathematical review: linear algebra, finite fields, polynomials, probabiliy theory (throughout the class)
Fast matrix multiplication (Strassen), verifying matrix multiplication, finding triangles in graphs [notes]