Andreas Jakoby

FOCS Conference 2010 Conference Paper

Logspace Versions of the Theorems of Bodlaender and Courcelle

• Michael Elberfeld
• Andreas Jakoby
• Till Tantau

Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula φ and for every k there is a linear-time algorithm that decides whether a given logical structure A of tree width at most k satisfies φ. We prove that both theorems still hold when "linear time" is replaced by "logarithmic space. " The transfer of the powerful theoretical framework of monadic second-order logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the log space world.

TCS Journal 2009 Journal Article

Improving the average delay of sorting

• Andreas Jakoby
• Maciej Liśkiewicz
• Rüdiger Reischuk
• Christian Schindelhauer

In previous work we have introduced an average case measure for the time complexity of Boolean circuits. Instead of fixed circuit depth, for each input we take the minimal number of time steps necessary to perform the computation for that particular input using gates that forward their output values as soon as possible. This measure is called delay. Based on it, the complexity of a whole class of functions that can be described as prefix computations has been analysed in detail. Here we consider the problem to sort large integers that are given in binary notation. Contrary to a word comparator sorting circuit C where a basic computational element, a comparator, is charged with a single time step to compare two elements, in a bit comparator circuit C ′ a comparison of two binary numbers has to be implemented by a Boolean subcircuit CM called comparator module that is built from Boolean gates of bounded fanin. Thus, compared to C, the depth of C ′ will be larger by a factor up to the depth of CM. Our goal is to minimize the average delay of bit comparator sorting circuits. The worst-case delay can be estimated by the depth of the circuit. For this worst-case measure two topologically quite different designs seem to be appropriate for the comparator modules: a tree-like one if the inputs are long numbers, otherwise a linear array working in a pipelined fashion. Inserting these into a word comparator circuit we get bit level sorting circuits for binary numbers of length m, for which the depth is either increased by a multiplicative factor of order log m or by an additive term of order m. We show that these obvious solutions can be improved significantly by constructing efficient sorting and merging circuits for the bit model that only suffer a constant factor time loss on the average if the inputs are uniformly distributed. This is done by designing suitable hybrid architectures of tree compaction and pipelining. These results can also be extended to classes of nonuniform distributions if we put a bound on the complexity of the distributions themselves.

TCS Journal 2007 Journal Article

Communications in unknown networks: Preserving the secret of topology

• Markus Hinkelmann
• Andreas Jakoby

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.

I&C Journal 1999 Journal Article

Malign Distributions for Average Case Circuit Complexity

• Andreas Jakoby
• Rüdiger Reischuk
• Christian Schindelhauer

In contrast to machine models like Turing machines or random access machines, circuits are a static computational model. The internal information flow of a computation is fixed in advance, independent of the actual input. Therefore, size and depth are natural and simple measures for circuits and provide a worst-case analysis. We consider a new model in which an internal gate is evaluated as soon as its result has been determined by a partial assignment of its inputs. This way, a dynamic notion of delay is obtained which gives rise to an average case measure for the time complexity of circuits. In a previous paper we have obtained tight upper and lower bounds for the average case complexity of several basic Boolean functions. This paper examines the asymptotic average case complexity for the set of alln-ary Boolean functions. In contrast to worst case analysis a simple counting argument does not work. We prove that with respect to the uniform probability distribution almost all Boolean functions require at leastn−log n−loglog nexpected time. On the other hand, there is a significantly large subset of functions that can be computed with a constant average delay. Finally, for an arbitrary Boolean function we compare its worst case and average case complexity. It is shown that for each function that requires circuit depthd, i. e. of worst-case complexityd, the expected time complexity will be at leastd−log n−log dwith respect to an explicitly defined probability distribution. In addition, a nontrivial upper bound on the complexity of such a distribution will be obtained.

STOC Conference 1994 Conference Paper

Circuit complexity: from the worst case to the average case

• Andreas Jakoby
• Rüdiger Reischuk
• Christian Schindelhauer