Structure, algorithms, and lower bounds.
Polynomials are perhaps the most important functions in mathematics. They feature in celebrated results from both antiquity and modern times. The goal of this lecture is to study polynomials from a computational perspective.
We will start out elementary, but will quickly arrive at important open research problems. The lecture will be based in part on the booklet
“Partial derivatives in arithmetic complexity (and beyond)”
by Xi Chen, Neeraj Kayal and Avi Wigderson
(Foundations and Trends in Theoretical Computer Science, 2011),
which is available online .
Die Vorlesung beginnt am Donnerstag, den 16. April.
|Vorlesung||Donnerstag||1215-1345||MA 376||Prof. Dr. Peter Bürgisser
|Übung||Dienstag||1415-1545||H 2038||Jesko Hüttenhain
exercise sheets provide additional material for the lecture. It is not
necessary to hand them in to be allowed to write the exam. However, we
highly recommend that you work on some of the problems.
- Exercise session 1 
- Exercise session 2 
- Exercise session 3 
- Exercise session 4 
No exercise session on 2nd June because of Peter Bürgisser's talk in the Oberseminar of the group Diskrete Mathematik / Geometrie .
Possible dates for the oral exams are as follows.
- August 17th-21st.
- October 12th-16th.
If you want to take an exam, sign in via QISPOS. This should be done in the time between 29th of June and 6th of July (for the first period) or between 7th of September and 2nd of October (for the second period).
In addition you will have to settle a date for your exam. This can be done at Beate Nießen 's office (MA 318), any day of the week except mondays and the weekend from 9:30 a.m. until 11:30 a.m.
Hinweis. Der Modulname für die mündliche Prüfung in "Multivariate Polynomials" ist Fortgeschrittene Themen der Algebra, 5 Leistungspunkte.
- arithmetic complexity,
- lower bounds,
- partial derivatives,
- identity testing,
- polynomial equivalence testing.
Chapter 1 Motivation and models of computation
- Symmetries of polynomials
- Arithmetic circuits and formulas
Chapter 2 Lower Bounds
- Provably hard polynomials
- Computation of derivatives
- Bezout's inequality
- Degree bound
Chapter 3 Structure
- A combinatorial algorithm for the determinant
- Formulas and branching programs
- Complexity classes
- Completeness results