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.

 

Homework 1

Homework 2

 

 

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)