|
 Mi, 27.4.2005
|
Georgios Mertzios (Ansprechpartner Sven Kosub)
Algorithmen für Clustererkennungsprobleme mit festen Parametern
|
|
Wir beschäftigen uns hier mit der
Komplexität vom fixed-parameter
cluster-detecting problem. Es handelt
sich um die Bestimmung eines Teilgraphs mit
bestimmter Größe und bestimmtem
konstanten Kantenüberschuss. Der einzige
bis jetzt bekannte Algorithmus löst das
Problem in Zeit $O(n^{2c+4})$, wenn angewendet
auf einen Graphen mit $n$ Knoten und $m$
Kanten, wobei $c$ der feste Parameter des
Problems ist. Wir präsentieren hier zwei
verbesserte Algorithmen mit Komplexität
$O(n^{2c+2})$ und
$O(\min{n^{2c+2},nm^{c+2}+n^{c+4}})$ im worst
case. Der Zweite von denen ist wesentlich
besser für dünnere Graphen. Der
Erste ist auch auf das Problem der Messung der
Design-Komplexität angewendet und hat die
Komplexität $O(n^{2c})$ in worst case zur
Folge.
|
|
|
Mi, 4.5.2005
|
Sandeep Sadanandan (Ansprechpartner Peter Ullrich)
Hyperelliptic Curves and Addition in their Jacobian
|
|
|
|
|
Mi, 11.5.2005
|
Oleg Verbitsky, Humboldt University of Berlin (Ansprechpartner Helumt Veith)
Descriptive Complexity of Finite Graphs
|
|
Given a finite graph, how succinctly can we
describe it using first order logic and the
laconic language consisting of the adjacency
and the equality relations? Among reasonable
succinctness measures we focus on the
quantifier depth of a first order
sentence. The minimum quantifier depth of a
sentence defining a graph up to isomorphism is
referred to as the first order depth of the
graph. This graph invariant is characterizable
in terms of the length of Ehrenfeucht's game
on non-isomorphic graphs. The subject is
linked to random graph theory (0-1 laws),
finite model theory and logic (Hilbert's
Entscheidungsproblem), and descriptive
complexity theory (graph isomorphism
testing). We will survey recent work and
discuss open questions in the area.
|
|
|
Mi, 18.5.2005
|
Matthias Baumgart
Approximation unabhängiger Mengen in Graphen
|
|
Eine unabhängige Menge in einem Graphen
ist eine Teilmenge der Knotenmenge mit
paarweise nicht benachbarten Knoten. Das
Bestimmen einer bezüglich
Kardinalität maximalen unabhängigen
Menge in einem Graphen
(Independent-Set-Problem) ist als NP-schwer
bekannt. Aus diesem Grund versucht man gute
Lösungen zu approximieren. Vorgestellt
wird ein Approximationsalgorithmus von Feige
zur Lösung des Independent-Set-Problems
mit Güte $O(n(\log\log n)^2 / (\log n)^3)$.
|
|
|
Mi, 22.6.2005
|
Stefan Katzenbeisser
Model Checking Malicious Code
|
|
The ease of compiling malicious code from source code in higher
programming languages has increased the volatility of malicious
programs: The first appearance of a new worm in the wild is usually
followed by modified versions in quick succession. As demonstrated by
Christodorescu and Jha, however, classical detection software relies
on static patterns, and is easily outsmarted. In this talk, we
present a flexible method to detect malicious code patterns in
executables by model checking. While model checking was originally
developed to verify the correctness of systems against specifications,
we argue that it lends itself equally well to the specification of
malicious code patterns. To this end, we introduce the specification
language CTPL (Computation Tree Predicate Logic) which extends the
well-known logic CTL, and describe an efficient model checking
algorithm. Our practical experiments demonstrate that we are able to
detect a large number of worm variants with a single specification.
|
|
|
Mi, 13.7.2005
|
|
