**Algebraic Gems of
Theoretical Computer Science**

**Seminar in Computer Science 16:198:672**

**Instructor:** Shubhangi Saraf

**Email:** shubhangi.saraf@gmail.com

**Timing: **Mon, Wed 3:20pm – 4:40 pm

**Location: **HILL 005

**Office hours: **Wed 1pm – 2 pm (Hill 426)

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.

No background in algebra will be 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.

**Schedule:**

§
**Lecture 1
(Wed 09/05): **Administrative details, course overview, linear algebra review

§
**Lecture 2
(Mon 09/10): **Odd-town, Even-town, fast matrix multiplication (Strassen), integer multiplication,

** **Verifying matrix multiplication,
finding triangles in graphs

§
**Lecture 3
(Wed 09/12): **Fast polynomial multiplication using FFT

§
**Lecture 4
(Mon 09/17): **Fast polynomial division, Graph spectrum

§
**Lecture 5
(Wed 09/19): **Eigenvalues and expanders, edge expansion, random walks on
expanders

§
**Lecture 6
(Mon 09/24): **More expanders - expander mixing, randomness reduction

§
**Lecture 7
(Wed 09/26):** Introduction to Error Correcting Codes

§
**Lecture 8
(Mon 09/01):** Basic bounds for codes

§
**Lecture 9
(Wed 09/03): **Codes based on polynomials, Reed Solomon Codes, Reed Muller
Codes, Schwartz-Zippel
Lemma

§
**Lecture
10 (Mon 10/08):** Berlekamp-Welch Algorithm for
decoding RS codes

§
**Lecture
11 (Wed 10/10):** Bounds for Kakeya Sets, Local
algorithms for Codes, Permanent is random self reducible

§
**Lecture
12 (Mon 10/15):** Cancelled

§
**Lecture
13 (Wed 10/17):** Guest lecture by Raghu: Linear algebraic techniques for
discrepancy

§
**Lecture
14 (Mon 10/22):** Method of multiplicities

§
**Lecture
15 (Wed 10/24):** Razborov Smolensky:
Lower bounds for AC0 circuits

§
**Lecture
16 (Mon 10/29):** Cancelled due to Sandy

§
**Lecture
17 (Wed 10/31):** Cancelled due to Sandy

§
**Lecture
18 (Mon 11/05):** Interactive Proofs:

§
**Lecture
19 (Wed 11/07): **#SAT in IP

§
**Lecture
20 (Mon 11/12): CANCELLED **(Makeup class on Nov 30, 1pm- 4pm, in Core A 301)

§
**Lecture
21 (Wed 11/14): CANCELLED **(Makeup class on Nov 30, 1pm- 4pm, in Core A 301)

§
**Lecture
22 (Mon 11/19):** Polynomial identity testing, graph matchings

**Useful references/related material:**

§ Linear algebra method: Blog post by Gowers

§ Course notes by Madhu Sudan (Algebra and computation)

§ Beautiful survey on expanders by Hoory, Linial and Wigderson

**A tentative (and partial)
list of topics that we will cover:**

· Applications of linear algebra

o (Eigenvalues and expansion in graphs, Applications of dimension and rank arguments, random projections)

· Polynomials in cryptography and complexity theory

o (Secret sharing, Secure multiparty computation, IP = PSPACE, PCP theorem)

· Design and analysis of error correcting codes (encoding and decoding algorithms) and other combinatorial structures, construction of pseudorandom objects such as randomness extractors and pseudorandom generators

· Applications of Fourier analysis

· Introduction to arithmetic circuits/arithmetic computation and polynomial identity testing

**Grading:** 70% homework and 30% presentation

**Homework:** There will be 2 or 3 problem sets over the
semester

**Presentations:** Students will be required to give short
presentations on research papers on topics related to the material we will
cover in class. Suggested topics for the presentations will be provided later
on.

**Some References:**

· 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)

**Related Courses:**

·
Algebra and Computation (by Madhu
Sudan)

·
Polynomials and Computation (by David Zuckerman)

·
Algebraic Methods in Combinatorics and Computer
Science (by Amir Shpilka)