Fakultät für Informatik - Technische Universität München
Lehrstuhl für Effiziente Algorithmen
|
|
Fakultät für Informatik - Technische Universität MünchenLehrstuhl für Effiziente Algorithmen |
|
| Acyclic Type-of-Relationship Problems on the Internet |
| Guaranteeing routing stability on the Internet is the
challenge for each network administration. While intra-domain
routing is under almost complete control by administrators,
inter-domain routing is based on contracts among independent
Internet players. These contracts are reflected in
different import-export policies for exchanging BGP routing
informations and thus may cause restricted reachibility for
users. It is thus important for efficient trouble shooting
to be able to infer such policies from data observable from the
Internet. In this talk we consider the problem of how to infer the contractual relationships (customer-provider, peer-to-peer, sibling-to-sibling) between autonomous systems on basis of BGP routing table entries. Based on appropriate notions of acyclicity in the network of business interrelationships we discuss algorithmic solutions for related combinatorial optimiztation problems. Experiments on real-world data show that the algorithms obtained produce the least number of misclassifications compared to standard algorithms.
Talk given:
Material available online.
|
| Fixed-Point Analysis of Boolean Dynamical Systems |
We present dichotomy results for the complexity of finding and counting fixed
points of boolean dynamical systems, i.e., discrete dynamical systems over the
domain {0,1}. For a class F of boolean functions and a class G of graphs
an (F,G)-system is a boolean dynamical system with its local transition functions
belonging to F and its underlying network belonging to G. We show that the
following complexity classification holds when local transition functions are
given by lookup tables: Let F be a class of boolean functions which is closed
under superposition and let G be a graph class closed under taking minors.
The talk is based on joint work with Christopher M. Homan (Rochester).
Talk given:
Material available online.
|
| Cluster Computing and the Power of Edge Recognition |
|
We study the robustness - the invariance under definition changes - of the cluster class CL#P.
This class
contains each #P function that is computed by a balanced Turing machine whose accepting paths always form
a cluster with respect to some length-respecting total order with efficient adjacency checks. The definition
of CL#P is heavily influenced by the defining paper's focus on (global) orders. In contrast, we define a
cluster class, CLU#P, to capture what seems to us a more natural model of cluster computing. We prove that
the naturalness is costless: CL#P = CLU#P. Then we exploit the more natural, flexible features of CLU#P to
prove new robustness results for CL#P and to expand what is known about the closure properties of CL#P. The complexity of recognizing edges - of an ordered collection of computation paths or of a cluster of accepting computation paths - is central to this study. Most particularly, our proofs exploit the power of unique discovery of edges - the ability of nondeterministic functions to, in certain settings, discover on exactly one (in some cases, on at most one) computation path a critical piece of information regarding edges of orderings or clusters.
Talk given:
Material available online.
|
| Shortest Path Mechanisms |
| In the Internet, coordination among entities (such as routers, servers, etc.) which are under control
by several parties is realized by protocols. Reasonably expecting these parties to follow their own
interests and desires, it is assumed that protocols are not necessarily complied; particularly, if it is in
the partie's own interest to cheat. Protocol design is to be provided with incentives in order to achieve
system adequate behavior. In mechanism design, the standard method is the VCG mechanism which encourages the
parties to report their true preferences by means of payments (of special type).
This survey talk centers around the mechanism design problem of selecting a shortest path in a network where
edges
(connections) are possessed by selfish parties. How costly can it be to find a shortest path? To answer this
question we give a brief, systematic introduction into the theory of implementation (aka mechanism design,
theory of incentives) and we discuss recent results on shortest path mechanisms.
Talk given:
Material available online:
|
| Boolean NP-Partitions and Projective Closure |
| When studying complexity classes of partitions one often faces the
situation that different partition classes have the same component
classes. The projective closures are the largest classes among these
with respect to set inclusion. In this talk we investigate projective
closures of classes of boolean NP-partitions, i.e., partitions
consisting of components that have complexity upper-bounds in the
boolean hierarchy over NP. We prove that the projective closures of
these classes are represented by finite labeled posets. We give
algorithms for calculating these posets and related problems. As a
consequence we obtain interesting new representations of the set
classes NP(m) intersected coNP(m) by means of finite labeled posets.
Talk given:
Material available online:
|
| Density-Based Clustering |
| Edge-density notions for graphs provide approaches central to managing several network clustering
issues. As an example, many of today's internet search engines use ranking and search methods
based on identifying groups of web sites highly connected by hyperlinks. Also VLSI layout design employs
density-based approaches; e.g., subgraphs having a certain edge density are used to obtain
hierarchical graph representations in order to decompose large circuits. How difficult it can be to
recognize dense subgraphs is of particular interest from an algorithmic perspective.
This talk presents
some algorithmic techniques and hardness results concerning this computational issue.
Talk given:
Material available online:
|
| Algorithms on Streams |
| The ever increasing relevance of interactive embeddings of computation has lead to a series of
new theoretical models and notions. On-line algorithms and competitive analysis are well-known examples.
Since many permanent information-processing issues can be described adequately only by means of
infinite data-streams, new approaches have been developed to manage these issues. Two algorithmic models
are presented and discussed in this talk: (a) the sliding windows model of Datar, Gionis,
Indyk and Motwani, and (b) the notion of conditional and essential computability.
Talk given:
Material available online:
|
| The Polynomial World of Complexity: P, PSPACE, and in between |
| In this survey talk an overview on definitions, characterizations, properties, and locations of
important complexity classes between P and PSPACE is given. Among the classes considered are, e.g., the
polynomial hierarchy, the boolean hierarchy, query hierarchies, probabilistic classes, the counting
hierarchy, the MOD hierarchy, Arthur-Merlin games, low and high hierarchies.
Survey talk given:
Material available online:
|
| Generic Separation and Leaf Languages |
| In the early nineties of the previous century, leaf languages were introduced
as a means for the uniform characterization of many complexity classes, mainly in the range between P
(polynomial time) and PSPACE (polynomial space). It was shown that the relativized separability of two
complexity classes can be reduced to a combinatorial property of the corresponding defining leaf
languages. In this talk, it is shown that every separation obtained in this way holds for every generic
oracle in the sense of Blum and Impagliazzo. We obtain several consequences of this result, regarding,
e.g., simultaneous separations and universal oracles, resource-bounded genericity, and type-2 complexity.
Talk given: Material not yet available online.
|
| The Boolean Hierarchy of NP-Partitions |
| Complexity theory is primarily concerned with the complexity of sets, i.e.,
with partitionings of a basic set into two parts. In this talk we deal with the
study of the complexity of partitions into k parts. For that, we generalize
the definition of the classes of the boolean hierarchy of sets by defining, for each
function mapping from {0,1}^m to {1,2,...,k}, a partition class NP(f)
of k-partitions. Whereas in the case of k=2, each of these classes coincides
with one of the classes NP(n) or coNP(n), in the case of k at least 3 the situation
turns out to be much more complicated. We give a sufficient criterion for inclusion
NP(f) contained in NP(g) depending solely on a relation between functions f and g; and we
provide evidence for the conjecture that our criterion is also necessary unless the polynomial
hierarchy is infinite.
Talk given: Material not yet available online.
|
| NP-Partitions over Posets with an Application to Reducing the Set of Solutions of NP Problems |
| The boolean hierarchy of k-partitions over NP for k at
least 3 was introduced as a generalization of the well-known boolean hierarchy
of sets (2-partitions). The classes of this hierarchy are exactly those classes
of NP-partitions which are generated by finite labeled lattices. We generalize
the boolean hierarchy of NP-partitions by studying partition classes which
are defined by finite labeled posets. We give an exhaustive answer to the
question of which relativizale inclusions between partition classes can occur
depending on the relation between their defining posets. This provides
additional evidence for the validity of the Embedding Conjecture for lattices. The study of the generalized boolean hierarchy is closely related to the issue of whether one can reduce the number of solutions of NP problems. For finite cardinality types, assuming the generalized boolean hierarchy of k-partitions over NP is strict, we give a complete characterization when such solution reductions are possible. This resolves in some sense an open question by Hemaspaandra, Ogihara, and Wechsung.
Talk given: Material not yet available online.
|
| On Cluster Machines and Unambigous Function Classes |
| We consider a special kind of nondeterministic Turing machines. Cluster machines
are distinguished by a neighborhood relationship among accepting paths. Based on
a formalization using equivalence relations some subtle properties of the machines
are proven. Moreover, by abstraction we gain the machine-independent concept of
cluster sets which is the starting point to establish cluster operators.
Cluster operators map complexity classes to function classes where for the
complexity classes only cluster sets are allowed. For the counting operator
c# and the optimization operators cmax and cmin we investigate structural
relationships between the images resulting from these operators in application
to the polynomial hierarchy. We prove statements like cmax P=cmin P and
c#P=FP iff UP=P.
Furthermore, we compare cluster operators with the corresponding common operator
#,max, and min. In this connection it is possible to prove some interesting facts,
e.g., c#P=#P iff PP=UP.
Talk given: No material available online.
|
May 23, 2007, Theory seminar (Habilitation colloquium), Lehrstuhl für Effiziente
Algorithmen, Technische Universität
München.