- Jan Arpe, Rüdiger Reischuk:
Learning Juntas in the Presence of Noise.
Theoretical Computer Science, 1(384):2-21, 2007.
Go to website - Jens Gramm, Till Nierhoff, Roded Sharan, Till Tantau:
Haplotyping with Missing Data via Perfect Path Phylogenies.
Discrete and Applied Mathematics, 155:788-805, 2007.
Show abstract
Computational methods for inferring haplotype information from genotype data are used in studying the association between genomic variation and medical condition. Recently, Gusfield proposed a haplotype inference method that is based on perfect phylogeny principles. A fundamental problem arises when one tries to apply this approach in the presence of missing genotype data, which is common in practice. We show that the resulting theoretical problem is NP-hard even in very restricted cases. To cope with missing data, we introduce a variant of haplotyping via perfect phylogeny in which a path phylogeny is sought. Searching for perfect path phylogenies is strongly motivated by the characteristics of human genotype data: 70% of real instances that admit a perfect phylogeny also admit a perfect path phylogeny. Our main result is a fixed-parameter algorithm for haplotyping with missing data via perfect path phylogenies. We also present a simple linear-time algorithm for the problem on complete data.
- Markus Hinkelmann, Andreas Jakoby:
Communications in unknown networks: Preserving the secret of topology.
Theoretical Computer Science, 384(2-3):184-200, 2007.
Show abstract
In cryptography we investigate security aspects of data distributed in a network. This kind of security does not protect the secrecy of the network topology against being discovered if some kind of communication has taken place. But there are several scenarios where the network topology has to be a part of the secret.
In this paper we study the question of communication within a secret network where the processing nodes of the network have only partial knowledge (e.g. given as routing tables) of the topology. We introduce a model for measuring the loss of security of the topology when far distance communication takes place. A communication protocol preserves the secret of topology if no processing node can deduce additional information about the topology from the communication. We will investigate lower bounds on the knowledge that can be revealed from the communication string and show, for instance, that some knowledge about distances can always be revealed. Then, we consider routing tables. We show that several kinds of routing tables are not sufficient to guarantee the secrecy of topology. On the other hand, if a routing table allows us to specify the direction from which a message is coming, we can run a protocol solving the all-to-all communication problem such that no processing node can gain additional knowledge about the network.
Finally, we investigate the problem of whether routing tables can be generated from the local knowledge of the processing nodes without losing the secrecy of the network topology with respect to the resulting knowledge base. It will be shown that this is not possible for static networks and most kinds of dynamic networks.
- Bodo Manthey, Rüdiger Reischuk:
Smoothed Analysis of Binary Search Trees.
Theoretical Computer Science, 378(3):292-315, 2007.
Go to website | Show abstract
Binary search trees are one of the most fundamental data structures. While the height of such a tree may be linear in the worst case, the average height with respect to the uniform distribution is only logarithmic. The exact value is one of the best studied problems in average-case complexity. We investigate what happens in between by analysing the smoothed height of binary search trees: Randomly perturb a given (adversarial) sequence and then take the expected height of the binary search tree generated by the resulting sequence. As perturbation models, we consider partial permutations, partial alterations, and partial deletions. On the one hand, we prove tight lower and upper bounds of roughly @Q((1-p)@?n/p) for the expected height of binary search trees under partial permutations and partial alterations, where n is the number of elements and p is the smoothing parameter. This means that worst-case instances are rare and disappear under slight perturbations. On the other hand, we examine how much a perturbation can increase the height of a binary search tree, i.e. how much worse well balanced instances can become.
- Till Tantau:
Logspace Optimization Problems and Their Approximability Properties.
Theory of Computing Systems, 41(2):327-350, 2007.
Show abstract
Logspace optimization problems are the logspace
analogues of the well-studied polynomial-time
optimization problems. Similarly to them, logspace
optimization problems can have vastly different
approximation properties, even though the underlying
decision problems have the same computational
complexity. Natural problems -- including the
shortest path problems for directed graphs,
undirected graphs, tournaments, and forests --
exhibit such a varying complexity. In order to study
the approximability of logspace optimization
problems in a systematic way, polynomial-time
approximation classes and polynomial-time reductions
between optimization problems are transferred to
logarithmic space. It is proved that natural
problems are complete for different logspace
approximation classes. This is used to show that
under the assumption L \neq NL some logspace
optimization problems cannot be approximated with a
constant ratio; some can be approximated with a
constant ratio, but do not permit a logspace
approximation scheme; and some have a logspace
approximation scheme, but cannot be solved in
logarithmic space.
- Jan Arpe, Rüdiger Reischuk:
When Does Greedy Learning of Relevant Attributes Succeed? - A Fourier-based Characterization.
In 13th Annual International Conference, Computing and Combinatorics, COCOON 2007, Volume 4598 of Lecture Notes in Computer Science, pp. 296-306.
Springer,
2007.
Go to website - Edith Hemaspaandra, Lane A. Hemaspaandra, Till Tantau, Osamu Watanabe:
On the Complexity of Kings.
In Proceedings of FCT 2007, Volume 4639 of Lecture Notes in Computer Science, pp. 328--340.
Springer,
2007.
Show abstract
A k-king in a directed graph is a node from which
each node in the graph can be reached via paths of
length at most~k. Recently, kings have proven
useful in theoretical computer science, in
particular in the study of the complexity of
reachability problems and semifeasible sets. In
this paper, we study the complexity of recognizing
k-kings. For each succinctly specified family of
tournaments (completely oriented digraphs), the
k-king problem is easily seen to belong to
$\Pi_2^{\mathrm p}$. We prove that the complexity of
kingship problems is a rich enough vocabulary to
pinpoint every nontrivial many-one degree in
$\Pi_2^{\mathrm p}$. That is, we show that for every
$k \ge 2$ every set in $\Pi_2^{\mathrm p}$ other
than $\emptyset$ and $\Sigma^*$ is equivalent to a
k-king problem under $\leq_{\mathrm m}^{\mathrm
p}$-reductions. The equivalence can be instantiated
via a simple padding function. Our results can be
used to show that the radius problem for arbitrary
succinctly represented graphs is $\Sigma_3^{\mathrm
p}$-complete. In contrast, the diameter problem for
arbitrary succinctly represented graphs (or even
tournaments) is $\Pi_2^{\mathrm p}$-complete.
- Markus Hinkelmann, Andreas Jakoby, Peer Stechert:
t-Private and Secure Auctions.
In 4th International Conference on Theory and Applications of Models of Computation (TAMC 2007), Volume 4484 of Lecture Notes in Computer Science, pp. 486-498.
Springer,
2007.
- Christian Hundt, Maciej Liskiewicz:
On the Complexity of Affine Image Matching.
In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS 2007), Volume 4393 of Lecture Notes in Computer Science, pp. 284-295.
Springer,
2007.
Go to website - Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk, Christian Schindelhauer:
Improving the Average Delay of Sorting.
In 4th International Conference, Theory and Applications of Models of Computation, TAMC 2007, Volume 4484 of Lecture Notes in Computer Science, pp. 330-341.
Springer,
2007.
Go to website - Andreas Jakoby, Till Tantau:
Logspace Algorithms for Computing Shortest and Longest Paths in Series-Parallel Graphs.
In Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), Volume 4855 of Lecture Notes in Computer Science, pp. 216-227.
Springer,
2007.
Show abstract
For many types of graphs, including directed acyclic graphs, undirected graphs, tournament
graphs, and graphs with bounded independence number, the shortest path problem is NL-complete.
The longest path problem is even NP-complete for many types of graphs, including undirected K5-minor-free graphs and even planar graphs. In the present paper we present logspace algorithms
for computing shortest and longest paths in series-parallel graphs where the edges can be directed
arbitrarily. The class of series-parallel graphs that we study can be characterized alternatively as the
class of K4-minor-free graphs and also as the class of graphs of tree-width 2. It is well-known that
for graphs of bounded tree-width many intractable problems can be solved efficiently, but previous
work was focused on finding algorithms with low parallel or sequential time complexity. In contrast,
our results concern the space complexity of shortest and longest path problems. In particular, our
results imply that for graphs of tree-width 2 these problems are L-complete.
- Rüdiger Reischuk:
Designing Boolean Sorting Circuits with Optimal Average Delay.
In Oberwolfach Reports X, Mathematisches Forschungsinstitut Oberwolfach,
2007.
- Matthias Schmalz, Hagen Völzer, Daniele Varacca:
Model Checking Almost All Paths Can Be Less Expensive Than Checking All Paths.
In Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2007), Volume 4855 of Lecture Notes in Computer Science, pp. 532-543.
Springer,
2007.
Show abstract
We compare the complexities of the following two model checking problems: checking whether a linear-time formula is satisfied by all paths (which we call universal model checking) and checking whether a formula is satisfied by almost all paths (which we call fair model checking here). For many interesting classes of linear-time formulas, both problems have the same complexity: for instance, they are PSPACE-complete for LTL.
In this paper, we show that fair model checking can have lower complexity than universal model checking, viz., we prove that fair model checking for L(F???) can be done in time linear in the size of the formula and of the system, while it is known that universal model checking for L(F???) is co-NP-complete. L(F???) denotes the class of LTL formulas in which F??? is the only temporal operator. We also present other new results on the complexity of fair and universal model checking. In particular, we prove that fair model checking for RLTL is co-NP-complete.
- Johannes Textor, Jürgen Westermann:
Modeling Migration, Compartmentalization, and Exit of Naive T Cells in Lymph Nodes Without Chemotaxis.
In 6th International Conference on Artificial Immune Systems (ICARIS 2007), Volume 4628 of Lecture Notes in Computer Science, pp. 228-239.
Springer,
2007.
Show PDF | Go to website | Show abstract
The migration of lymphocytes through secondary lymphoid
organs was believed to be mainly controlled by chemokine gradients.
This theory has recently been called into question since naive lymphocytes observed in vivo by two-photon microscopy show no evidence of
directed migration. We have constructed a simple mathematical model
of naive T cell migration in lymph nodes that is solely based on local
mechanisms. The model was validated against ?ndings from histological
analysis and experimentally determined lymphocyte recirculation kinetics. Our results suggest that T cell compartmentalization in lymph nodes
can be explained without long-range chemokine gradients. However, the
T cell residence time predicted by our model is signi?cantly lower than
observed in vivo, indicating the existence of a mechanism which alters
the T cell random walk over time.
