Office: TAY 3.134
Office Hours: Tu 5-6, F 4-5
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 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.|
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
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