General Info:

### Tentative schedule of topics:

### 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

- NEW: Please
signup for your project presentations. Availability + Instructions

- The course now has a blog at http://algebraandcomputation.wordpress.com.

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

- Lecture 01 (Wed.
02/08): CANCELLED.
- Lecture 02 (Mon.
02/13): Administrivia, Course
Contents. Membership in permutation groups. Notes
((updated 2/21/2012) tex, pdf).
- Lecture 03 (Wed.
02/15): Review of algebra: Existence
and Uniqueness of Fields. Notes ((updated 3/10/2012) tex, pdf).
- Monday (02/20):
President's Day holiday.
- Lecture 04 (Tue.
02/21): Computation with
polynomials - basic problems. Fast polynomial
multiplication. Prenotes (pdf).
Notes (tex, pdf).
- Lecture 05 (Wed.
02/22): CANCELLED.
- Lecture 06 (Mon.
02/27): Fast polynomial
division, GCD. Prenotes (pdf). Notes ((updated
3/8/2012) tex, pdf).
- Lecture 07 (Wed.
02/29): Polynomial
factorization: Randomized over all fields; deterministic
over fields of small characteristic. Prenotes (pdf). Notes (tex, pdf).
- Lecture 08 (Mon.
03/05): Factorization
of multivariate polynomials. Bezout's theorem.
Prenotes (pdf). Notes (tex, pdf)
- Lecture 09 (Wed.
03/07): Guest Lecturer: Eli
Ben-Sasson. The
Lenstra-Lenstra-Lovasz (LLL) algorithm. Prenotes (pdf). Notes (tex, pdf).
- Lecture 10 (Mon.
03/12): Hensel Lifting. (Incomplete) Prenotes (pdf). Notes (tex, pdf).
- Lecture 11 (Wed.
03/14): Factorization of
multivariate polynomials - conclusion. Prenotes (pdf). Notes ((updated
4/12/2012) tex, pdf).
- Lecture 12 (Mon.
03/19): Primality testing. Prenotes (pdf). Notes (tex, pdf).
- Lecture 13 (Wed. 03/21): Guest Lecturer: Eli Ben-Sasson. Extracting randomness from algebraic sources. Notes (tex, pdf).
- (03/26-03/30): Spring Break
- Lecture 14 (Mon.
04/02): Systems of polynomial
equations: Some problems. Notes (tex, pdf).
- Lecture 15 (Wed.
04/04): Ideal membership
problem. Gröbner basis. Prenotes (pdf). Notes (tex, pdf).
- Lecture 16 (Mon.
04/09): Complexity of Ideal Membership. Prenotes (pdf).
Notes (tex, pdf).
- Lecture 17 (Wed. 04/11): Hilbert Nullstellensatz. Quantifier elimination. Prenotes (pdf). Notes (tex, pdf).
- (Mon. 04/16 + Tue. 04/17): Patriots Day holiday.
- Lecture 18 (Wed.
04/18): Arithmetic Complexity: Models, Problems, Classes,
Basic Stuff. Prenotes (pdf).
Notes (tex, pdf).

- Lecture 19 (Mon 04/23): Polysize
circuit for determinant. Depth Reduction. Partial
Derivatives. Prenotes (pdf). Notes (tex, pdf).
- Lecture 20 (Wed.
04/25): Lower bounds for multi-point polynomial
evaluation. Strassen's proof. Smolensky's proof. Prenotes
(pdf). Notes (tex, pdf).
- Lecture 21 (Mon.
04/30): Applications of
Algebra in Computing: Codes and Decoding. Prenotes (pdf). Notes (tex, pdf)
- Lecture 22 (Wed.
05/02): Applications of
Algebra in Computing: Probababilistically Checkable
Proofs. Prenotes (pdf).
Notes (tex, pdf).
- Lecture 23 (Mon. 05/07): Applications of Algebra in Computing: Locally Decodable Codes. Prenotes (pdf). Notes (tex, pdf).
- Project Presentations:
Day 1 (Time TBD).

- Lecture 24 (Wed. 05/09): Locally decodable codes of [Yekhanin, Raghavendra, Efremenko]. Prenotes (pdf). Notes (tex, pdf).
- Project
Presentations: Day 2 (Time TBD).

- Lecture 25 (Mon.
05/14): CANCELLED.
- Lecture 26 (Wed.
05/16): CANCELLED.

- Notes from Fall 98: The full set and the website.
- Notes from Fall 2005: the website.
- Survey by Amir Shpilka and Amir Yehudayoff.