Vorlesung über "Algebraische Komplexitätstheorie"

Behandlung folgender Themen:

• Grundlegende Polynomiale Algorithmik
• Valiants Theorie und die Komplexität der Permanente
• Reduktions- und Vollständigkeitsbegriff
• (Komplexitätsresultate für) kryptographische Verfahren
• Polynombasen
• Diskrete Fourier-Transformation: Algorithmik u. Anwendungen
• Graphisomorphieproblem
• Blum-Shub-Smale-Modell

Literatur

• J. von zur Gathen, J. Gerhard, Modern Computer Algebra, Cambridge University Press, 2003.
• M. Kaplan, Computeralgebra, Springer-Verlag, 2005.
• U. Schoening, Algorithmik, Spektrum-Verlag, 2001.
• A. Salomaa, Public-Key Cryptography, Springer-Verlag, 1996.
• P. Buergisser, Completeness and Reduction in Algebraic complexity theory, Springer-Verlag, 2000.
• P. Buergisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997.
• Blum, Shub, Tucker, Smale, Computing over the reals, 1999.
• J. Koebler, U. Schoening, J. Toran, The graph isomorphism problem: its structural complexity, Birkhaeuser, 1993.