Sie sind hier

# 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.

## 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
Übung
Dienstag
1415-1545
H 2038
Jesko Hüttenhain

## Ü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.

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

# 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'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

## Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

## Hilfsfunktionen

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.