General Info:

### Tentative Schedule (topics of lectures are
still TBD):

### References:

- Lecturer: Madhu Sudan; 32-G640; email: first name at mit dot edu
- TA: None.
Voluntary help welcome.

- Units: 3-0-9 H Level Grad Credit;
- Time and Location: MW 11-12:30 in 34-304

- PS1 posted (tex, pdf).
Due Friday, March 6, 2015. Solutions (tex, pdf).

- Course announcement
- Grading Policy
- Scribe availability (Sample files for scribes: sample.tex; Uses: preamble.tex and fullpage.sty)

- Lecture 01 (Wed.
02/04): Administrivia, Course Contents.
Membership in permutation groups. Prenotes (pdf). Notes (tex, pdf).
- Lecture 02 (Mon.
02/09): Madhu out of town -
Lecture contents and Lecturer TBD
- Lecture 03 (Wed.
02/11): Madhu out of town - Lecture contents and Lecturer TBD
- Monday (02/16):
President's Day holiday.
- Lecture 04 (Tue.
02/17): Review of algebra: Existence and
Uniqueness of Fields. Notes (tex, pdf).
- Lecture 05 (Wed.
02/18): Computation with polynomials - basic problems.
Fast polynomial multiplication. Prenotes from Spring
2012 (pdf).
Notes (tex, pdf).
- Lecture 06 (Mon.
02/23): Fast polynomial
division, GCD; Factorization - 1. Prenotes from
Spring 2012 (here,
here,
and here).
Notes (tex, pdf).
- Lecture 07 (Wed.
02/25): Polynomial
factorization: Randomized over all fields; deterministic
over fields of small characteristic. Minimal
polynomials. Prenotes from Spring 2012 (pdf).
Notes (tex, pdf).
- Lecture 08 (Mon.
03/02): Factorization
of multivariate polynomials. Resultant. Bezout's theorem.
Prenotes from Spring 2012 (pdf).
Notes (tex, pdf).
- Lecture 09 (Wed.
03/04): Factorization of bivariate polynomials (contd.).
Notes + Addendum (tex,
pdf).
- Lecture 10 (Mon.
03/09): Fatorization of univariate polynomials over the
rationals. Notes (tex, pdf).
- Lecture 11 (Wed.
03/11): The LLL algorithm for
finding short vectors in lattices. Prenotes from Spring
2012 (pdf).
Notes (tex, pdf).
- Lecture 12 (Mon.
03/16): Primality testing-1. Prenotes from Spring 2012 (pdf).
Notes (tex, pdf).
- Lecture 13 (Wed.
03/18): Primality testing-2. Notes (tex, pdf).

- (03/23-03/28): Spring Break
- Lecture 14 (Mon.
03/30): Arithmetic Complexity: Models, Problems,
Classes, Basic Stuff. Prenotes from
Spring 2012 (pdf).
Notes (tex, pdf).
- Lecture 15 (Wed.
04/01): Polysize circuit for determinant. Depth
Reduction. Partial Derivatives. Prenotes
from Spring 2012 (pdf).
Notes (tex, pdf).
- Lecture 16 (Mon.
04/06): Depth Reduction (contd.).
Notes (tex, pdf).
- Lecture 17 (Wed. 04/08): Lower bounds for multi-point polynomial evaluation. Strassen's proof. Smolensky's proof. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
- Lecture 18 (Mon.
04/13): Smolensky's proof contd. Determinant,
Permanent. Depth 4 circuits and lower bounds.
Notes (tex,
pdf).

- Lecture 19 (Wed. 04/15): Conclude
arithmetic circuits. Complexity of Ideal membership,
Nullstellensatz etc. Notes (tex, pdf).
- (Mon. 04/20 + Tue. 04/21): Patriots Day holiday.
- Lecture 20 (Wed. 04/22): Ideal membership and Groebner bases. Prenotes from Spring 2012 (pdf). Notes (tex, pdf).
- (Thu.
04/23): DROP DATE.

- Lecture 21 (Mon.
04/27): Complexity of Ideal
Membership. Hilbert Nullstellensatz. Quantifier
Elimination. Prenotes from Spring 2012 (pdf).
Notes (tex, pdf).
- Lecture 22 (Wed.
04/29): Applications of
Algebra in Computing: Codes and Decoding. Notes (tex,pdf).
- Lecture 23 (Mon. 05/04): Applications of Algebra in Computing: Folded Reed-Solomon Codes. Locally Decodable Codes. Prenotes (pdf). Notes (tex, pdf).
- Lecture 24 (Wed. 05/06): Locally decodable codes of [Yekhanin, Raghavendra, Efremenko]. Prenotes (pdf). Notes (tex, pdf).
- Lecture 25 (Mon.
05/11): Project presentations.
- Lecture 26 (Wed.
05/13): Project presentations.

- Notes from Fall 98: The full set and the website.
- Notes from Fall 2005: the website.
- Notes from Spring
2012: the website.

- Survey by Amir Shpilka and Amir Yehudayoff.