Class: Tuesdays & Thursdays 11-12:20, CSE (EBU3B) 2154

Instructor: Shachar Lovett, email: slovett@ucsd.edu

Office hours: Thursdays after class (12:30-2pm), CSE 4234

TA: Jiapeng Zhang, email: jpeng.zhang@gmail.com

Office hours: Fridays 2-3p, CSE 4232

Grading: Homework and take-home exam

Problem set 1, due April 21

Problem set 2, due May 5

Problem set 3, due May 28

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.

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.

- Mathematical review: linear algebra, finite fields, polynomials, probabiliy theory (throughout the class)
- Fast matrix multiplication (Strassen), verifying matrix multiplication, finding triangles in graphs [notes]
- Fast polynomial multiplication and FFT [notes]
- Secret sharing scheme [notes]
- Introduction to error correcting codes, basic bounds for codes [notes]
- Reed-Solomon codes, Berlekamp-Welch algorithm for decoding [notes]
- Polynomial identity testing, Schwarz-Zippel Lemma, finding perfect matchings in graphs [notes]
- Solving satisfiability via random walks [notes]
- Pairwise independent hash functions and applications [notes]
- Karger's min-cut algorithm [notes]
- Randomized routing [notes]
- Expander graphs [notes]

- Randomized algorithms book, by Motwani and Raghavan
- Advanced algorithm design course in Princeton, by Arora [link]
- Pairwise independence and its applications, by Luby and Wigderson [link]
- Expander graphs and their applications, by Hoory, Linial and Wigderson [link]
- Survey on fast matrix multiplication, by Filmus [part 1] [part 2]