SS 2014 » Algebraic Complexity Theory



13.05.2014Due to a time conflict, the lecture intended for May 20 has to be moved to Monday, June 2nd at 2:25pm in S2/15-244 (!)
22.04.2014Based on the Doodle poll we have agreed today to have lectures from now on on Tuesdays 13h30-15h10; and exercises on Mondays 15h20-16:05.
19.04.2014First exercises session will be on Tuesday, April 22, from 13:30 to 15:10 (90 minutes!) and serve also to discuss the future schedule.
11.04.2014First session starts on Monday, April 14, at 1:30pm.
In view of the holiday on next Monday (April 21st)
we will for once use the first exercise session on April 15 (Tuesday, 2:25pm) for lectures.



Name Raum Tel.
Ziegler, Martin



TagUhrzeitin Raum
Dienstags13:30 - 15:10S2/15-201





Nr.Zeitin Raum
1Montags, 15:20 - 16:05S2/15-201



Efficient algorithmic solutions have always been among the major goals of mathematics: Euclidean GCD calculation, Gaussian Elimination, Fast Fourier Transform, and Simplex are some prominent examples. Algebraic Complexity Theory studies the intrinsic computational difficulty of problems within an algebraic model of computation. We devise and analyze the cost of algorithms for polynomial evaluation and multiplication, matrix multiplication, point location, or solvability of systems of polynomial in-/equalities; and we prove them (essentially) optimal by asserting that any algorithm solving such a problem must incur a certain cost, asymptotically. Such lower complexity bounds generally follow quantitatively from the growth of sophisticated invariants; or structurally by comparison to (formally: reduction from) other problems.

  1. Motivating Examples for Algebraic Models of Computation

  2. Examples of (Almost) Tight Complexity Bounds
    1. Nonscalar Cost of Polynomial Multiplication: Interpolation and Dimension bound
    2. Discrete Fourier Transform: FFT and Volume bound
    3. Nonuniform Polynomial Evaluation: Preconditioning and Transcendence degree
  3. Efficient Algorithms for Polynomial Arithmetic
    1. Multiplication of Polynomials
    2. Newton's Method for Polynomial Division
    3. Multipoint Evaluation of Polynomials
    4. Baur-Strassen: Partial Derivatives for Free
    5. Multiplication by Structured Matrices
  4. Complexity of Matrix Multiplication
    1. Strassen's Algorithm
    2. Complexity and Tensor Rank of Bilinear Maps
    3. Properties of the Tensor Rank
    4. Exponent of Matrix Multiplication, LUP-Decomposition, and Inversion
    5. Multipoint Evaluation of Bivariate Polynomials
  5. Branching Complexity
    1. Semialgebraic and Projective Geometry
    2. Ben-Or's Lower Bound and Applications
    3. Range Spaces and their Vapnik-Chervonenkis Dimension
    4. Fast Point Location in Arrangements of Hyperplanes
    5. Polynomial-depth Algorithms for NP-complete Problems
  6. NP-Completeness over the Reals
    1. Blum-Shub-Smale machines over the Reals
    2. Feasibility of a system of polynomial in-/equalities
    3. Solvability of a quadratic polynomial equation
    4. Equation over the Crossproduct
    5. Satisfiability in Quantum Logic
    6. Realizability of an oriented Matroid
    7. Stretchability of Pseudolines



Achtung: Vom 23.10.2017 bis 25.10.2017 ist das Studienbüro wegen Semestervorbereitung geschlossen! Die Sprechstunden entfallen!

Ordnungen, Formulare, etc.

Dokumente wie Prüfungsplan-formulare, Studien- und Prüfungspläne oder Modulhandbücher finden Sie im Downloadbereich

Sabine Bartsch
Iryna Bysaha
Meike Mühlhäußer
Alexandra Neutsch
Bettina Plutz (in Elternzeit)

Mi, Do10:30-12:30



 Albrun Knof


Die Sprechstunden finden in Raum S2|15 241 statt. Es ist keine Terminvereinbarung notwendig.

Weitere Fragen bitte per Mail an:




A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang