207568668
Parallel Prefix Computation
The prefix problem is to compute all the products x t o x2 . . . . o xk for i ~ k .~ n, where o is an associative operation A recurstve construction IS used to obtain a product circuit for solving the prefix problem which has depth exactly [log:n] and size bounded by 4n An application yields fast, small Boolean ctrcmts to simulate fimte-state transducers. By simulating a sequentml adder, a Boolean clrcmt which has depth 2[Iog2n] + 2 and size bounded by 14n Is obtained for n-bit binary addmon The size can be decreased significantly by permitting the depth to increase by an addmve constant
15236721
Bounds on secret key exchange using a random deal of cards
We present a general model for communication among a “team” of players overheard by a passive eavesdropper, Eve, in which all players including Eve are given private inputs that may be correlated. We define and explore secret key exchange in this model. Our secrecy requirements are information-theoretic and hold even if Eve is computationally unlimited. In particular, we consider the situation in which the team players are dealt hands of cards of prespecified sizes from a known deck of distinct cards. We explore when the team players can use the information contained in their hands to determine a value that each team player knows exactly but Eve cannot guess.
2458859
Impossibility of distributed consensus with one faulty process
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. We show that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the "Byzantine Generals" problem.
207660233
Impossibility of distributed consensus with one faulty process
The consensus problem involves an asynchronous system of processes, some of which may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of nontermination, even with only one faulty process. By way of contrast, solutions are known for the synchronous case, the “Byzantine Generals” problem.
7656106
Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
We study algorithmic aspects in the management of geometric scenes in interactive walkthrough animations. We consider arbitrarily large scenes consisting of unit size balls. For a smooth navigation in the scene we have to fulfill hard real time requirements. Therefore, we need algorithms whose running time is independent of the total number of objects in the scene and that use as small space as possible. In this work we focus on one of the basic operations in our walkthrough system: reporting the objects around the visitor within a certain distance. 
 
Previously a randomized data structure was presented that supports reporting the balls around the visitor in an output sensitive time and allows insertion and deletion of objects nearly as fast as searching. These results were achieved by exploiting the fact that the visitor moves "slowly" through the scene. A serious disadvantage of the aforementioned data structure is a big space overhead and the use of randomization. 
 
Our first result is a construction of weak spanners that leads to an improvement of the space requirement of the previously known data structures. Then we develop a deterministic data structure for the searching problem in which insertion of objects are allowed. Our incremental data structure supports O(1+k) reporting time, where k is a certain quantity close to the number of reported objects. The insertion time is similar to the reporting time and the space is linear to the total number of objects.
29746533
Guidance of Users in Interactive 3D-Visualisations of Material Flow Simulations
1648746
Experience in early and late software engineering project courses
We report on the experience we gained in different software engineering project courses at our department. A student who is specialized in software engineering has to complete, besides lectures on software engineering and related fields, two project courses: an "early" basic project course, and a "late" complex project course. For both of them we developed leveled teaching approaches considering the different knowledge and skills of beginners and "advanced" students, respectively. The paper describes, discusses and evaluates these approaches.
9204420
Partitioned neighborhood spanners of minimal outdegree
A geometric spanner with vertex set P IRD is a sparse approximation of the complete Euclidean graph determined by P. We introduce the notion of partitioned neighborhood graphs (PNGs), unifying and generalizing most constructions of spanners treated in literature. Two important parameters characterizing their properties are the outdegree k IN and the stretch factor f 1 describing the ‘quality’ of approximation. PNGs have been thuroughly investigated with respect to small values of f . We, on the other hand, present in this work results about feasable values of k — so to say the other extreme. The aim of minimizing this parameter rather than the first one arises from two observations: a) It determines the amount of space required for storing PNGs. b) Many algorithms employing a (previously constructed) spanner have running times depending on its outdegree. Our results include, for fixed dimensions D as well as asymptotically, upper and lower bounds on this optimal value of k. The upper bounds are constructive and yield efficient algorithms for actually computing the corresponding graphs. 1Partially supported by EU ESPRIT Long Term Research Project 20244 (ALCOM-IT) and DFG Grants Me872/7-1 and Me872/4-1
6874024
Optimal Layout of Edge-weighted Forests
The layout problem for trees with weighted edges is motivated by the design of very-large-scale integrated circuits. Some of the nodes are fixed and the object is to position the remainder so that the total weighted edge cost is minimized. The cost of each edge is the product of its weight and its length under some appropriate norm. Optimization for planar layouts is shown to be NP-hard. If crossings are permitted, then optimal layouts under the L1 norm can be efficiently computed. Suitable algorithms and data structures are presented, and explicit exact cost functions are given for two classes of weighted complete binary trees.