wanka@uni-paderborn.de (Rolf Wanka) (01/24/91)
13. Workshop
Komplexitaetstheorie und effiziente Algorithmen
Paderborn, 5.2.91, RaumE1.143
Programm:
9.15 Imbiss
10.00 Begruessung
10.05 Ingo Althoefer (Bielefeld): Data Compression with Artificial
Intelligence: The Storage of Chess Master Games as an Example
10.25 Dirk Theune (Paderborn): Das algebraische Wegeproblem
10.45 Rudolf Fleischer, Bhabani Sinha, Christian Uhrig (Saarbruecken):
A lower bound for the worst case of the number of comparisons of
bottom-up-heapsort
11.05 PAUSE
11.20 Johannes Bloemer (Berlin): Wie man schnell entscheidet, ob
eine Summe von Wurzeln rational ist
11.40 Otfried Schwarzkopf (Berlin), Jack Snoeyink (Utrecht):
Berechnung minimaler umschliessender Kreisringe
12.00 Hans Georg Osthof (Saarbruecken): Ein Scaling-Algorithmus
fuer den gewichteten kleinsten einschliessenden Kreis R^d
12.20 MittagsPAUSE
14.20 Kurzb eitraege und offene Probleme:
- Marek Karpinski, Barbara Lhotzky (Bonn): Effizienter
Approximationsalgorithmus fuer multilineare Funktionen
ueber GF[q]
- Christoph Meinel, Stephan Waack (Berlin): Separating
complexity classes related to bounded alternating
omega-branching programs
- Gerhard Buntrock (Wuerzburg), Birgit Jenner,
Klaus-JoernLange, Peter Rossmanith (Muenchen):
Unambiguity und Fewness fuer logarithmischen Platz
- Ondrej Sykora, Imrich Vrto (Saarbruecken): Edge separators
for graphs of genus g with applications
- H. Schroeder, Ondrej Sykora, Imrich Vrto (Saarbruecken):
Optimal embeddings of a torus on a linear array
.
.
15.20 Peter Zienicke (Berlin): Einbettung von Hyperwuerfeln in
2-dimensionale Gitter
15.40 Matthias Krause (Berlin): Kommunikationskomplexitaet Boolescher
Funktionen, Algebraische Charakterisierungen und neue Resultate
16.00 KaffeePAUSE
16.40 Gerhard Lischke (Jena): Starke und schwache Separationen
ohne Prioritaetsmethode
17.00 Edmund Ihler (Freiburg): Approximation and Existential
Second-Order Logic
17.20 Krzysztof Lorys (Wuerzburg): New Time Hierarchy Results
for Deterministic TMs
17.40 Ulrich Hertrampf, Klaus Wagner (Wuerzburg): Interaktive
Proof Systeme: Prover, Runden, Fehlerwahrscheinlichkeiten
18.00 SCHLUSS