In diesem Seminar sollen Vorträge zu wechselnden Themen aus den Bereichen Computeralgebra, Kombinatorik und Komplexitätstheorie stattfinden.
Kriterium für den Scheinerwerb ist ein Vortrag mit Ausarbeitung.

Die Teilnehmenden sind unter dem Verteiler seminarca at math zu erreichen.

Material zu LaTeX:
The Not So Short Introduction to LaTeX 2\epsilon.

Termin: Mittwoch, 16:00-17:30 in J2.130

Vorbesprechung: Montag, den 18.10.2004 um 11:00 Uhr

Beginn: Mittwoch, den 3. November

Vorträge

3.11.04	Die Berechnungskomplexität des Hilbertpolynoms von glatten projektiven Varietäten Martin Lotz Zusammenfassung Das Hilbertpolynom ist eine der wichtigsten Invarianten projektiver Varietäten (Nullstellenmengen von Systemen von Polynomgleichungen im projektiven Raum): aus ihm lassen sich u.a. die Dimension, der Grad und das Geschlecht der Varietät ablesen. Bekannte Algorithmen zur Berechnung des Hilbertpolynoms können exponentiell viel Platz beanspruchen. Es soll hier gezeigt werden, dass das Problem der Berechnung des Hilbertpolynoms im Falle glatter Varietäten nicht schwieriger ist als das Zählen der Anzahl Lösungen von polynomialen Gleichungssystemen. Dieses Problem ist in polynomialem Platz lösbar. Literatur D. Bayer and D. Mumford: What can be computed in algebraic geometry?, In: Computational algebraic geometry and commutative algebra (Cortona 91), Sympos. Math, Cambridge, 1993 P. Bürgisser and M. Lotz: The complexity of computing the Hilbert polynomial of smooth equidimensional complex projective varieties, 2005
10.1.04	Machine Independent Characterizations of Complexity Classes in the BSS Model of Computations (Im Rahmen des PaSCo Oberseminar) Paulin Jacobé de Naurois Zusammenfassung We focus on the BSS model of computation over arbitrary structures, introduced in 1989 By L.Blum, M.Shub and S.Smale to denote computations over the real numbers, and later on extended to computations over arbitrary structures. This model can be seen as an extention of the classical Turing machines. In particular, complexity classes extending the classical one are defined, andcomplete problems in these classes are found. Moreover, over many structures, the question whether deterministic and non-deterministic polynomial time coincide seems as difficult and as intersting as in the classical Turing model of computation. In this talk, we briefly present this model of computation, and extend many classical techniques for syntactically characterizing complexity classes. We extend some results by Grädel, Gurevich and Meer in descriptive complexity, characterizing deterministic and non deterministic polynomial time decision problems in terms of logics over metafinite structures. We also define a notion of partial and primitive recursive functions over arbitrary structures, and extend some results by Bellantoni and Cook, characterizing functions computable in sequential determinisitc polynomial time, and by Leivant and Marion, characterizing functions computable in parallel determinisitc polynomial time in terms of algebras of recursive functions. We also provide some characterizations of functions computable within the polynomial hierarchy and in polynomial alternating time. Literatur Siehe Homepage.
17.11.04	Komplexität der Zerlegung einer algebraischen Varietät in irreduzible Komponenten Peter Scheiblechner Zusammenfassung Jede algebraische Varietät über den komplexen Zahlen lässt sich in eindeutiger Weise in ihre irreduzible Komponenten zerlegen, die nicht weiter in nicht trivialer Weise als Vereinigung algebraischer Varietäten darstellbar sind. Es ist momentan noch nicht klar, ob sich diese Zerlegung in polynomialem Platz berechnen lässt. Giusti und Heintz haben 1990 gezeigt, dass die Zerlegung in äquidimensionale Komponenten, d.h. die Vereinigung der irreduziblen Komponenten gleicher Dimension, in polynomialem Platz möglich ist. Es soll hier eine weitere Reduktion dieses Problems auf den Fall von rein eindimensionalen Varietäten (Kurven) vorgestellt werden. Literatur M. Giusti and J. Heintz: Algorithmes - disons rapides - pour la decomposition d'une variete algebrique en composantes irreductibles et equidimensionelles. In: Proceedings of MEGA'90 (1991), T. Mora and C. Traverso, Eds., vol. 94 of Progress in Mathematics, Birkhauser, pp. 169-194. D. Bayer and D. Mumford: What can be computed in algebraic geometry?, In: Computational algebraic geometry and commutative algebra (Cortona 91), Sympos. Math, Cambridge, 1993 P. Bürgisser, F. Cucker, M. Lotz: Counting Complexity Classes for Numeric Computations III: Complex Projective Sets C.Bajaj, J. Canny, T. Garrity, J. Warren: Factoring Rational Polynomials over the Complexes, International Conference on Symbolic and Algebraic Computation, Proc. ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, Portland, Oregon, United States, pp. 81 - 90
24.11.04	Die erwartete Anzahl reeller Nullstellen von zufälligen (Systemen von) Polynomen Ulrich Prior Literatur A. Edelman and E. Kostlan: How many zeros of a random polynomial are real?, Bulletin of the AMS, 32, 1995 L. Blum, F. Cucker, M. Shub and S. Smale: Complexity and Real Computation, Springer 1998
1.12.04	Polynomzeitalgorithmen für Permutationsgruppen Julia Borghoff Literatur Furst, Merrick, J. Hopcroft and E. Luks: Polynomial-time algorithms for permutation groups. 21st Annual Symposium on Foundations of Computer Science (Syracuse, N.Y., 1980), pp. 36--1, IEEE, New York, 1980. Weiteres: W. Bosma und J. Cannon: Structural computation in finite permutation groups, CWI-Quarterly, vol. 5, pp. 127-160, 1992 (siehe auch hier). P. Köhler: Gruppentheoretische Algorithmen (WS 00/01), Vorlesungskript Uni Giessen T. Beth, M. Grassl: Algorithmen für Gruppen und Codes (WS03/04), Vorlesung an der Uni Karlsruhe A. Seress: Permutation Group Algorithms, Cambridge 2003 Ausarbeitung: [ pdf ]
8.12.04	Seminar fällt aus!!!
15.12.04	Ein Polynomialzeitalgorithmus für das Graphenisomorphieproblem bei trivalenten Graphen Christiane Peters Literatur E. Luks: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. System Sci. 25 (1982), no. 1, 42--65. Ausarbeitung: [ pdf ]
22.12.04	Bestimmung der Konvergenzrate von Irrfahrten auf endl. Gruppen mittels Darstellungstheorie Andreas Kottmann Literatur P. Diaconis: Group representations in probability and statistics, Institute of Mathematical Statistics, Hayward, 1988.
12.1.05	Untere Schranken für multilineare Formelgrösse Thomas Sauerwald Literatur R. Raz: Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size, STOC 2004 R. Raz: Multilinear-NC_1 \neq Multilinear-NC_2, FOCS 2004 Beide Arbeiten sind auf der Seite von Ran Raz erhältlich. Ausarbeitung: [ pdf ]
19.1.05	Seminar fällt aus !!!
26.1.05	Die mittlere Berechnungskomplexität zur Auswertung der Permanente Christian Ikenmeyer Literatur J. Cai, A. Pavan, D. Sivakumar: On the Hardness of Permanent, STACS 1999 Die Arbeit ist hier erhältlich. Ausarbeitung: [ ps | pdf ]
2.2.05	Das quadratische Sieb Jingyi Wu Literatur J. von zur Gathen and Jürgen Gerhard: Modern Computer Algebra, Cambridge 2003 P. Bürgisser: Vorlesung Computeralgebra, Sommersemester 2002 T. Reinecke: Faktorisierung ganzer Zahlen