CS395T: Polynomials and Computation (Spring 2004)

Syllabus: Syllabus.
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Office: TAY 3.134
Phone: 471-9729
Office Hours: Tu 5-6, F 4-5
Course Overview: Several important advances in computer science have relied strongly on properties of polynomials. These advances include the deterministic primality test, the list decoding of Reed-Solomon codes, and the characterizations of classical complexity classes via interactive proofs and probabilistically checkable proofs. The elegance of many of these proofs is partly due to their reliance on simple properties of polynomials.

In this course, we will survey applications of polynomials in computer science. In the first 2/3 of the course, I will lecture on the following topics. The last 1/3 of the course will be student presentations.

Topic Reference(s)
Algebra Background Shoup's computational algebra book
Factoring Polynomials Sudan's Algebra and Computation course notes
Deterministic Primality Test Agrawal-Kayal-Saxena, Bornemann's overview
PARITY is not in AC0 Trevisan's notes on Razborov-Smolensky proof
List and Locally Decodable Codes Sudan's Coding Theory course notes
Polynomial-Based Extractors Ta-Shma-Zuckerman-Safra, Shaltiel-Umans, my talk
IP=PSPACE Shamir's original paper, Shen's simplification
Probabilistically Checkable Proofs Babai-Fortnow-Lund, FGLSS, Feige's notes, Sudan's notes

Problem Sets: Problem Set #1
Problem Set #2
Presentation Tips: You may use transparencies or the blackboard or some combination. Some helpful tips are available in Ian Parberry's Speaker's Guide. Please allow 5-10 minutes at the end for questions and comments on the presentation.
Presentation Schedule: Factoring bivariate and multivariate polynomials
Sudan's Algebra and Computation course notes
To be presented by Ned Dimitrov on April 5.

Cryptographic Hardness based on the Decoding of Reed-Solomon Codes with Applications
Kiayias-Yung
To be presented by Jesse Kamp on April 7.

Reconstructing curves in 3D from noisy data
Coppersmith-Sudan
To be presented by Anup Rao on April 12.

Testing Reed-Muller codes
Alon-Kaufman-Krivelevich-Litsyn-Ron
To be presented by Anindya Patthak on April 14.

The expressive power of voting polynomials
Aspnes-Beigel-Furst-Rudich
To be presented by Todd Geldon on April 19.

PP is closed under intersection
Beigel-Reingold-Spielman. Also see
PP is closed under truth-table reductions
Fortnow-Reingold
To be presented by Dan Fernholz on April 21.

Representing Boolean functions as polynomials modulo composite integers
Barrington-Beigel-Rudich
To be presented by Victor Chen on April 26.

Quantum Lower Bounds by Polynomials
Beals-Buhrman-Cleve-Mosca-Wolf
To be presented by Andy Mills on April 28.

The Tutte polynomial; Matroids, Codes and Their Polynomial Links
Chapters 2, 3, and 5 of Rutherford's thesis, plus handouts
To be presented by Wei David Zhao on May 3.

Derandomizing polynomial identity tests means proving circuit lower bounds
Kabanets-Impagliazzo
To be presented by Ryan Pai on May 5.


Last modified: April 21, 2004