 Mi,23.04.2003
|
Markus Holzer
Über komplexitätstheoretische Askepte des Tensor Kalküls
|
|
Tensorgleichungen und -ausdr"ucke finden h"aufig
Verwendung in der Physik, einigen Ingenieursdisziplinen und der
Informatik. Zum Beispiel finden bestimmte Tensorformel-Identit"aten
bei der Implementierung von blockrekursiven Algorithmen Anwendung. In
dieser Arbeit werden Evaluierungsprobleme von wohlgeformten
Tensorformeln und Tensorschaltkreisen "uber verschiedenen Halbringen
betrachtet. Dabei ergeben sich Charakterisierungen von
Standardkomplexit"atsklassen mit Hilfe vollst"andiger Probleme und
dar"uber hinaus einige weitere interessante Anwendungen in
verschiedenen Gebieten der Komplexit"atstheorie.
Quanten-Computings. Hier gelang es, deterministische und
probabilistische Berechnungen als nat"urlichen Spezialfall von
Quantenberechnungen darzustellen und somit den Weg f"ur eine
einheitliche Sichtweise verschiedener Berechnungsmodelle
vorzubereiten. Auf dieser Basis konnte eine einfache Klasse von
Problemen definiert werden, die f"ur einige probabilistische und
Quanten-Komplexit"atsklassen vollst"andig sind.
|
|
|
Mi,30.04.2003
|
Stefanie Gerke
The generalised acyclic edge chromatic
number of random regular graphs
|
|
The $r$-acyclic edge chromatic number of a graph is defined
to be the minimum number of colours required to produce an
edge colouring of the graph such that adjacent edges receive different
colours and any $k$-cycle has at least
$\min\{k,r\}$ colours, for $k\geq 3$.
We show that $2d$ is asymptotically almost surely (a.a.s.)
an upper bound on the $4$-acyclic edge chromatic number of a random
$d$-regular graph. This is joint work with Catherine Greenhill and
Nicholas Wormald.
|
|
|
Mi,14.05.2003
|
Christian Glaßer (Universität Würzburg)
Disjunkte NP-Paare
|
Ein disjunktes NP-Paar ist ein Paar (A,B),
wobei A und B Mengen aus NP mit leerem Schnitt
sind. Solche Paare sind von zwei Perspektiven
aus interessant: Zum einen besteht eine
Verbindung zur Kryptographie, genauer zur
Existenz von sicheren
Public-Key-Kryptosystemen. Andererseits gibt
es eine Beziehung zwischen disjunkten
NP-Paaren und aussagenlogischen
Beweissystemen.
Nach einer Einführung in dieses Gebiet
sehen wir uns den aktuellen Stand der
Forschung an und betrachten interessante
offene Fragestellungen.
Einige der vorzustellenden Resultate wurden
in Zusammenarbeit mit Alan Selman, Samik
Sengupta und Liyu Zhang erzielt.
|
|
|
Mi,21.05.2003
|
Sven Kosub
Algorithmen gegen Streams
|
|
Die immer stärker werdende Betonung interaktiver Einbettungen
algorithmischer Berechnungen hat von theoretischer Seite aus zu einer Reihe
neuer Modelle und Betrachtungsweisen geführt. Online-Algorithmen und
kompetitive Analyse stehen exemplarisch hierfür. Da viele permanent
anfallende Informationsverarbeitungsaufgaben adäquat nur mittels
unendlichen Datenströmen beschrieben werden können, sind auch hier
neue Ansätze entwickelt worden. In diesem Vortrag werden zwei
algorithmische Modelle vorgestellt und diskutiert: (a) Sliding
windows von Datar, Gionis, Indyk und Motwani sowie (b) bedingte und
wesentliche Berechenbarkeit aus eigener Forschung.
|
|
|
Mi,18.06.2003
|
Marcus Hutter, Senior Researcher, IDSIA (Forschungsinstitut für
Künstliche Intelligenz), Lugano, Schweiz
Optimale sequentielle Entscheidungen
basierend auf algorithmischer
Wahrscheinlichkeit
|
|
Eintscheidungstheorie löst das Problem
rationaler Agenten in ungewisser Umgebung,
falls die wahre a priori-
Wahrscheinlichkeitsverteilung der Umgebung
bekannt ist. Solomonoffs Theorie der
universellen Induktion löst formal das Problem
der Sequenz-Vorhersage im Falle unbekannter a
priori- Wahrscheinlichkeit. Der Kern dieses
Vortrages ist, beide Theorien zu einer
parameter- freien Theorie universeller
Künstlicher Intelligenz zu
vereinheitlichen. Wir präsentieren starke
Argumente dafür, dass das resultierende
AIXI-Modell der best-mögliche
universell-intelligente Agent ist. Wir
umreißen für eine Reihe von Problemen,
einschließlich Sequenz- Vorhersage,
Strategie-Spielen, Funktions-Minimierung,
Verstärkungs- und überwachtem Lernen, wie das
AIXI-Modell diese formal löst. Der größte
Nachteil des AIXI-Modells ist, dass es nicht
berechenbar ist. Um dieses Problem zu
überwinden, konstruieren wir einen
modifizierten Algorithmus AIXItl, der immer
noch effektiv intelligenter ist als jeder
andere bzgl. Zeit t und Länge l beschränkte
rationale Agent. Die Rechenzeit von AIXItl ist
von der Größenordnung t x 2^l. Die Diskussion
wird formale Definitionen von
Intelligenz-Ordnungs-Relationen, das
Horizont-Problem, und Relationen der
AIXI-Theorie zu anderen KI-Ansätzen
einschließen.
|
|
|
Mi,02.07.2003
|
Achtung: Ausnahmnsweise um 16:00
Uhr s.t.
Thomas Bayer
Konstruktive Stratifikation von Aktionen Kompakter Lie Gruppen
|
|
Ein alternativer Zugang zur Stratifikation (= Partitionierung) von R^n
bzw. den Orbitraum bzgl. der Aktion einer
kompakten Lie Gruppe wird vorgestellt. Die einzelnen Strata werden mit
polynomialen Gleichungen bzw.
Ungleichungen dargestellt, wobei die Anzahl der Ungleichungen gleich der
Dimension des jeweiligen Stratums ist.
Des weiteren wird ein Algorithmus vorgestellt, der den Orbitraum einer
kompakten Lie Gruppe durch d*(d-1)*1/2
viele Ungleichungen beschreibt (+ einer Anzahl von polynomialen
Gleichungen). Anwendungen finden sich beispielsweise in der Physik
(Symmetriebrechung) und Materialwissenschaft (Form-Gedaechtnismaterialien).
|
|
|
Mi,09.07.2003
|
Stefanie Gerke
Random Graphs with Constraints
|
|
Algorithms for networks like mobile telephone networks or
the world-wide-web are often difficult to evaluate. Such algorithms
often perform poorly in the worst case, but in practice they perform quite
well. To explain this behaviour one needs to understand how typical instances
look like. One standard model is the random graph which is constructed
by choosing the edges of a graph independently at random with
probability $p$. The random graph is well understood but
unfortunately it often does not represent the instances of interest
because they have more constraints attached to them. In this talk we
introduce some special models of random graphs with dependencies on the
edges and show some of their properties. For example we give a bound
on the number of edges of a random planar graph and determine
the acyclic edge chromatic number of a random regular graph. We also show
some cases of a "key"-lemma which allows us to find substructures in
sparse random graphs.
|
|
|
