direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Multivariate Polynomials

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 [1].

Vorlesungszeiten

Die Vorlesung beginnt am Donnerstag, den 16. April.

Zeiten
Veranstaltung
Tag
Dauer
Raum
Lehrperson
Vorlesung
Donnerstag
1215-1345
MA 376
Prof. Dr. Peter Bürgisser [2]
Übung
Dienstag
1415-1545
H 2038
Jesko Hüttenhain [3]

Übungen

The 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 [4]
  • Exercise session 2 [5]
  • Exercise session 3 [6]
  • Exercise session 4 [7]
    [8]

 

No exercise session on 2nd June because of Peter Bürgisser's talk in the Oberseminar of the group Diskrete Mathematik / Geometrie [9].

Mündliche Prüfungen

Possible dates for the oral exams are as follows.

  1. August 17th-21st.
  2. 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 [10]'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.

Inhalte

Keywords:

  • arithmetic complexity,
  • lower bounds,
  • symmetries,
  • partial derivatives,
  • identity testing,
  • polynomial equivalence testing.

Chapter 1 Motivation and models of computation

    1. Symmetries of polynomials
    2. Arithmetic circuits and formulas

    Chapter 2 Lower Bounds

    1. Provably hard polynomials
    2. Computation of derivatives
    3. Bezout's inequality
    4. Degree bound

    Chapter 3 Structure

    1. A combinatorial algorithm for the determinant
    2. Formulas and branching programs
    3. Complexity classes
    4. Completeness results
    ------ Links: ------

    Zusatzinformationen / Extras

    Direktzugang

    Schnellnavigation zur Seite über Nummerneingabe

    Copyright TU Berlin 2008