| 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.
|
||||||||||||||||
| 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 |
||||||||||||||||
| Homework policy: |
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 Disabilites: |
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. |