Zu einem endlichen metrischen Raum kann man ein konvexes Polyeder konstruieren, dessen Teilkomplex aller beschränkten Seiten als Tight Span bezeichnet wird. Seit den 1980er Jahren finden diese Objekte Verwendung bei Problemen der phylogentischen Rekonstruktion in der algorithmischen Biologie. Nach einer grundlegenden Einführung in die Thematik konzentriert sich der Vortrag vor allem auf die Frage, wieviele Seiten ein solcher Tight Span maximal haben kann.

Public key cryptography is an indispensable part of our modern communication systems. However, quantum computers can break the most commonlyused public key cryptosystems like RSA, which are based on “hard” number theory problems. Recently a great effort has been put into the search for alternative public key cryptosystems. Multivariate public key cryptosystems (MKPC), whose public key is a set of multivariate polynomials over a finite field, provide one such promising alternative. The theoretical security assumption comes from the fact that solving a system of polynomial equations over a finite field is in general NP-complete and quantum computers are not yet effective in solving this problem. Furthermore, computations in a finite field can be more efficient, therefore MPKCs also have the potential in application for devices with limited computing power. In this talk, we will first present an systematic introduction of the recent development in this new area, the focus will be on the the Matsumoto-Imai cryptosystems, the Sflash cryptosystems, the HFE cryptosystems, the Oil- Vinegar cryptosystems, the HFEv cryptosystems, the TTM cryptosystems, the cryptosystems of internal perturbation and the Rainbow cryptosystems, the related multivariate polynomial solving algorithms, and we will also present the main challenges we are currently facing.

In der Stahlproduktion gegossene Brammen, Barren von bis zu zwölf Meter Länge und zwanzig Tonnen Gewicht, müssen innerhalb gegebener Zeitfenster an der Strangussanlage entsorgt und meist vor der Weiterverarbeitung zwischengelagert werden. Um Lagerplatz effizient zu nutzen, werden sie auf Stapeln gelagert. Die Brammen sind nicht austauschbar und parallel zur Einlagerung müssen vorgegebene Stapel am Ausgang des Lagers zur Verfügung gestellt werden. Um den Durchsatz des Lagers zu erhöhen, soll die Gesamtanzahl notwendiger Krantransporte innerhalb des Lagers minimiert werden; insbesondere ist also häufiges Umstapeln von Brammen zu vermeiden. Wir stellen einen praxistauglichen Algorithmus aus dem Bereich der kombinatorischen Optimierung vor, welcher beweisbar sehr gute Lösungen für das beschriebene Problem liefert und auch leicht auf andere Logistikanwendungen übertragbar ist, in denen Güter gestapelt werden.

Dieser Vortrag handelt von einer exakten Lösungsmethode des Max-Cut Problems, ein NP-schweres kombinatorisches Optimierungsproblem. Grundlage dieses neuen Algorithmus ist ein Semidefinites Optimierungsproblem (SDO), dessen Lösung als obere Schranke an den maximalen cut verwendet wird. Da das Lösen dieses Semidefiniten Optimierungsproblems auf Grund der vielen Nebenbedingungen mit herkömmlichen Methoden nicht möglich ist, verwenden wir die sogenannte Bundle Methode, um das Problem `fast` optimal zu lösen. Diese Schrankenberechnung wird in einem Branch and Bound Verfahren eingebaut und all das zusammen nennen wir Biq Mac - a solver for BInary Quadratic and MAx-Cut problems. Im Vortrag wird das Max-Cut Problem erklärt und das SDO hergeleitet. Weiters wird die Bundle Methode, mit der das SDO gelöst wird, erläutert. Es werden viele numerische Resultate präsentiert und wir geben eine grobe Übersicht, wie sich die Rechenzeiten von Biq Mac mit jenen anderer exakter Lösungsmethoden vergleichen lassen.

Die Boltzmann-Gleichung ist die fundamentale Gleichung der kinetischen Gastheorie. Deren Lösung gibt die Verteilungsfunktion der Gasteilchen nach Zeit, Ort und Geschwindigkeit an unter der Annahme, dass die mittleren freien Weglängen der Teilchen groß sind. Man geht also von einem verdünnten Gas aus. Die Vorlesung beinhaltet die Einführung des Boltzmann-Modells und die Darlegung der grundlegenden Eigenschaften der Boltzmann-Gleichung.

Wavelets in Sobolev spaces are of interest in numerical algorithms, though most traditional wavelets are analyzed and constructed in the square integrable function space L^2(R). In this talk, we shall first present a short overview on some background of wavelets in L^2(R). Then we shall discuss pairs of dual wavelet frames (and Riesz wavelet bases) in Sobolev spaces H^s(R). We shall see that many classical results on wavelets in the space L^2(R) can be naturally extended into the setting of wavelets in Sobolev spaces. Finally, we shall discuss how to construct pairs of dual wavelet frames in Sobolev spaces via the projection method. Some examples will be provided to illustrate the theoretical results.

Die Defizite der gymnasialen Lehrerbildung im Fach Mathematik sind alt, gut beschrieben und unverändert aktuell. Das Tandemprojekt zwischen den Universitäten Gießen (Leitung: A. Beutelspacher) und Siegen (Leitung: R. Danckwerts) wagt einen Versuch, die fachliche Ausbildung angehender Gymnasiallehrer in den beiden ersten Studienjahren grundlegend neu zu orientieren. Inhaltliches Ziel ist es, die Schulmathematik, die Hochschulmathematik, die Geschichte und die Didaktik der Mathematik vom Studienbeginn an konsequent miteinander zu verzahnen. Die Studierenden sollen nicht nur, wie es meist üblich ist, die fertige Mathematik kennen lernen, sondern sie sollen von Anfang an in ihrem eigenen Lernprozess erleben, wie mathematisches Wissen entsteht. Berichtet wird über die Konzeption und erste Ergebnisse, hier in erster Linie über das Siegener Teilprojekt mit einer Neuorientierung des Lernbereichs Analysis.

In this talk, I will review recent developments in the area of cost-sharing mechanisms. Consider the following game- theoretic setting: a service is offered to a set of players. Each player`s goal is to receive service and she derives a certain (private) valuation from being serviced. A cost-sharing mechanism first collects bids from each of the players. Subsequently, the mechanism must a) select a subset of the player set to service, and b) decide on how much to charge each of the recipients. Three classical properties of a ``good`` mechanism are: 1) incentive compatibility - it is in the best interest of a rational player to bid truthfully, 2) budget-balance - the prices charged should recover the total cost of servicing the recipients, and 3) e±ciency - the set of recipients chosen should maximize (total valuation of serviced players { service cost). A well-known result due to Green, Kohlberg and Laffont states that no mechanism can achieve the above three properties simultaneously. Even worse, Feigenbaum, Papadimitriou and Shenker showed that these properties cannot even be achieved approximately. I will first survey recent results due to Roughgarden and Sundararajan in which the authors present an alternate definition of e±ciency. The authors also present tight bounds on the efficiency of so called Moulin mechanisms. In the second part of this talk, I will talk about e±cient mechanisms for Steiner forests and its prize-collecting variant. Joint work with A. Gupta, S. Leonardi, R. Ravi, and G. Schaefer

In vielen Anwendungen ist der Metropolis Algorithmus bei optimaler Temperatur mindestens so gut wie Simulated Annealing. Nachdem es lange nur künstlich konstruierte Gegenbeispiele gab, haben Jerrum und Sinclair es als ``outstanding open problem`` bezeichnet, ein natürliches Gegenbeispiel zu finden. Dieses Problem wird gelöst. Anschließend wird eine Komplexitätstheorie für Optimierungsprobleme vorgestellt, bei denen die Zielfunktion nur als ``black box`` gegeben ist.