| 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.
|
||||||||||||||||||
| 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
Reconstructing curves in 3D from noisy data
Testing Reed-Muller codes
The expressive power of voting polynomials
PP is closed under intersection
Representing Boolean functions as polynomials modulo composite integers
Quantum Lower Bounds by Polynomials
The Tutte polynomial;
Matroids, Codes and Their Polynomial Links
Derandomizing polynomial identity tests means proving circuit lower bounds
|