### Inhalt des Dokuments

### zur Navigation

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

Veranstaltung | Tag | Dauer | Raum | Lehrperson |
---|---|---|---|---|

Vorlesung | Donnerstag | 12^{15}-13^{45} | MA 376 | Prof. Dr. Peter Bürgisser |

Übung | Dienstag | 14^{15}-15^{45} | 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.

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

## Inhalte

Keywords:

- arithmetic complexity,
- lower bounds,
- symmetries,
- 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