On Numerical Invariants in Algebraic Complexity Theory
Martin Lötz · Amtliche Mitteilungen (Universitätsbibliothek Paderborn) · 2005
A common theme in mathematics is the classification of mathematical objects by assigning numerical invariants to them.There are two ways in which such numerical invariants can appear in relation to computational complexity.On the one hand, mathematical invariants are used in the context of proving lower complexity bounds: they serve as obstructions to the existence of fast algorithms for solving certain problems.On the other hand, it is the computational complexity of actually computing such invariants that is of interest.The first part of this thesis is concerned with lower bounds for the problems of computing linear and bilinear maps.The invariants used, namely the mean square volume, singular values, and rigidity, belong to linear algebra.One of the main results is a tight lower bound of order Ω(n log n) for the problem of multiplying two polynomials, in the model of bounded coefficient circuits.This lower bound is extended to circuits for which a limited number of unbounded scalar multiplications (help gates) are allowed.The second part is concerned with the complexity of actually computing numerical invariants.The objects of study are two of the most prominent invariants in algebraic geometry and topology: the Euler characteristic and the Hilbert polynomial of complex projective varieties.These problems are studied within the framework of counting complexity classes.It is shown that the problem of computing the Euler characteristic of a complex projective variety is on essentially the same level of difficulty as the problem of counting the number of solutions of a system of polynomial equations.A similar result is proved for the Hilbert polynomials, when the input variety is assumed to be smooth and equidimensional. DanksagungenAn erster Stelle möchte ich meinem Betreuer Peter Bürgisser herzlichst danken: Für seine Unterstützung und Leitung, seine Geduld, und für alles was ich von ihm gelernt habe (mathematisch, und auch sonst).Estoy muy agradecido a Felipe Cucker por invitarme a Hong Kong, donde parte de este trabajo fue escrito, y por su ayuda en varios aspectos.Darüber hinaus möchte ich mich bedanken bei:-Joachim von zur Gathen, für das Bereitstellen eines Teils meiner Stelle, sein Interesse an meiner Arbeit, und für wichtige Literaturhinweise.-Helmut Lenzing und dem Institut für Mathematik, für die hervorragenden Arbeitsbedingungen, und die Verlängerung meiner Stelle, was es mir ermöglicht hat die Arbeit hier zu beenden.