SoSe 2014 » Algebraic Complexity Theory
Ziegler

Übersicht

Downloads

Aktuelles

13.05.2014	Due 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.2014	Based 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.2014	First 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.2014	First 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.

 

Veranstalter

Name	Raum	Tel.
Ziegler, Martin

 

Vorlesung

Tag	Uhrzeit	in Raum
Dienstags	13:30 - 15:10	S2/15-201

 

Literatur

• Algebraic Complexity Theory (HeBIS, Buch Habel, Amazon)
• Completeness and Reduction in Algebraic Complexity Theory (HeBIS, Wellnitz, Buch Habel, Amazon)
• Complexity and Real Computation (HeBIS, Wellnitz, Buch Habel, Amazon)

 

Übung

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

 

Contents

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

 

Impressum | Datenschutzerklärung