CS395T: Polynomials and Computation (Spring 2004)

Logistics: MW 4:30-6:00
TAY 3.144
Unique Number: 51385
Course web page: http://www.cs.utexas.edu/users/diz/395T
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)
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 Local Decodable Codes Sudan's Coding Theory course notes
Polynomial-Based Extractors and PRG's Ta-Shma-Zuckerman-Safra, Shaltiel-Umans, Umans
IP=PSPACE Shamir's original paper, Shen's simplification
Probabilistically Checkable Proofs Sudan's PCP course notes

Prerequisites: CS 388C and an undergraduate Theory of Computation class such as CS 353. Students wishing to take this without CS 388C may discuss it with me.
Grading: 65%: Homework (probably two or three assignments)
35%: Presentations
Collaboration policy: I encourage you to discuss homework problems with your classmates. However, you must write up your own solutions. Furthermore, you must acknowledge any collaboration by writing the names of your collaborators on the front page of the assignment.

Citation policy: If you use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words.

Late policy: Each student has two late days that they can use during the semester with no penalty (one assignment two days late or two assignments one day late). Once late days are used up, no credit will be given for late assignments.

Paper Presentations: Each student will present for one or two lectures, depending on enrollment. You may work in groups. Possible topics include the use of Chebychev polynomials in CS, voting polynomials, representation of polynomials mod a composite, PP is closed under complement, and the difficulty of derandomizing polynomial identity tests. Specific paper suggestions will be given later in the semester.
Students with
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.