Certifying RSA - Kakvi, Saqib; Kiltz, Eike; May, Alexander (Advances in Cryptology – ASIACRYPT 2012)

Optimal Security Proofs for Full Domain Hash, Revisited - Kakvi, Saqib; Kiltz, Eike (Advances in Cryptology – EUROCRYPT 2012)

Continuous Local Strategies for Robotic Formation Problems - Kempkes, Barbara; Meyer auf der Heide, Friedhelm (Experimental Algorithms)

Local, Self-organizing Strategies for Robotic Formation Problems - Kempkes, Barbara; Meyer auf der Heide, Friedhelm (Algorithms for Sensor Systems)

Newton’s Method and Secant Method for Set-Valued Mappings - Baier, Robert; Molo, Mirko Hessel-von (Large-Scale Scientific Computing)

Bleichenbacher’s Attack Strikes again: Breaking PKCS#1 v1.5 in XML Encryption - Jager, Tibor; Schinzel, Sebastian; Somorovsky, Juraj (Computer Security – ESORICS 2012)

Asynchronous Occlusion Culling on Heterogeneous PC Clusters for Distributed 3D Scenes - Suess, Tim; Koch, Clemens; Jähn, Claudius; Fischer, Matthias; Meyer auf der Heide, Friedhelm (Advances in Visual Computing)
We present a parallel rendering system for heterogeneous PC clusters to visualize massive models. One single, powerful visualization node is supported by a group of backend nodes with weak graphics performance. While the visualization node renders the visible objects, the backend nodes asynchronously perform visibility tests and supply the front end with visible scene objects. The visualization node stores only currently visible objects in its memory, while the scene is distributed among the backend nodes’ memory without redundancy. To efficiently compute the occlusion tests in spite of that each backend node stores only a fraction of the original geometry, we complete the scene by adding highly simplified versions of the objects stored on other nodes. We test our system with 15 backend nodes. It is able to render a ≈ 350,M polygons (≈ 8.5,GiB) large aircraft model with 20, to 30,fps and thus allows a walk-through in real-time.

Evolving for Creativity: Maximizing Complexity in a Self-organized Multi-particle System - Hamann, Heiko; Schmickl, Thomas; Crailsheim, Karl (10th European Conference on Artificial Life (ECAL'09))

Modeling Agents and Agent Systems - Lettmann, Theodor; Baumann, Michael; Eberling, Markus; Kemmerich, Thomas (Transactions on Computational Collective Intelligence V)

Collisionless Gathering of Robots with an Extent - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; auf der Heide, Friedhelm Meyer; Raupach, Christoph; Swierkot, Kamil; et al. (SOFSEM 2011: Theory and Practice of Computer Science)

A New Approach for Analyzing Convergence Algorithms for Mobile Robots - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; et al. (Automata, Languages and Programming)

Exploiting New Interaction Techniques for Disaster Control Management Using Multitouch-, Tangible- and Pen-Based-Interaction - Nebe, Karsten; Klompmaker, Florian; Jung, Helge; Fischer, Holger Gerhard (Human-Computer Interaction. Interaction Techniques and Environments.)

A Holistic Model for Integrating Usability Engineering and Software Engineering Enriched with Marketing Activities - Fischer, Holger Gerhard; Nebe, Karsten; Klompmaker, Florian (Human Centered Design)

Collisionless Gathering of Robots with an Extent - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; et al. (37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011))
Gathering n mobile robots in one single point in the Euclidean plane is a widely studied problem from the area of robot formation problems. Classically, the robots are assumed to have no physical extent, and they are able to share a position with other robots. We drop these assumptions and investigate a similar problem for robots with (a spherical) extent: the goal is to gather the robots as close together as possible. More exactly, we want the robots to form a sphere with minimum radius around a predefined point. We propose an algorithm for this problem which synchronously moves the robots towards the center of the sphere unless they block each other. In this case, if possible, the robots spin around the center of the sphere. We analyze this algorithm experimentally in the plane. If R is the distance of the farthest robot to the center of the sphere, the simulations indicate a runtime which is linear in n and R. Additionally, we prove a theoretic upper bound for the runtime of O(nR) for a discrete version of the problem. Simulations also suggest a runtime of O(n + R) for the discrete version.

Energy-Efficient Strategies for Building Short Chains of Mobile Robots Locally - Brandes, Philipp; Degener, Bastian; Kempkes, Barbara; Meyer auf der Heide, Friedhelm (Structural Information and Communication Complexity)

Mixing Bottom-Up and Top-Down XPath Query Evaluation - Benter, Markus; Böttcher, Stefan; Hartel, Rita (East European Conference on Advances in Databases and Information Systems)

Updates on Grammar-Compressed XML Data - Bätz, Alexander; Böttcher, Stefan; Hartel, Rita (Advances in Databases - 28th British National Conference on Databases, BNCOD 28, Revised Selected Papers)

TraCX: Transformation of Compressed XML - Böttcher, Stefan; Hartel, Rita; Stey, Sebastian (Advances in Databases - 28th British National Conference on Databases, BNCOD 28, Revised Selected Papers)

A New Approach for Analyzing Convergence Algorithms for Mobile Robots - Cord-Landwehr, Andreas; Degener, Bastian; Fischer, Matthias; Hüllmann, Martina; Kempkes, Barbara; Klaas, Alexander; Kling, Peter; Kurras, Sven; Märtens, Marcus; Meyer auf der Heide, Friedhelm; Raupach, Christoph; Swierkot, Kamil; et al. (Automata, Languages and Programming)
Given a set of n mobile robots in the d-dimensional Euclidean space, the goal is to let them converge to a single not predefined point. The challenge is that the robots are limited in their capabilities. Robots can, upon activation, compute the positions of all other robots using an individual affine coordinate system. The robots are indistinguishable, oblivious and may have different affine coordinate systems. A very general discrete time model assumes that robots are activated in arbitrary order. Further, the computation of a new target point may happen much earlier than the movement, so that the movement is based on outdated information about other robot's positions. Time is measured as the number of rounds, where a round ends as soon as each robot has moved at least once. In [Cohen, Peleg: Convergence properties of gravitational algorithms in asynchronous robot systems], the Center of Gravity is considered as target function, convergence was proven, and the number of rounds needed for halving the diameter of the convex hull of the robot's positions was shown to be O(n^2) and Omega(n). We present an easy-to-check property of target functions that guarantee convergence and yields upper time bounds. This property intuitively says that when a robot computes a new target point, this point is significantly within the current axes aligned minimal box containing all robots. This property holds, e.g., for the above-mentioned target function, and improves the above O(n^2) to an asymptotically optimal O(n) upper bound. Our technique also yields a constant time bound for a target function that requires all robots having identical coordinate axes.

Como podemos definir vigilância? - Fuchs, Christian (MATRIZes)

Read-Write-Codes: An Erasure Resilient Encoding System for Flexible Reading and Writing in Storage Networks - Mense, Mario; Schindelhauer, Christian (Proceedings of 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems)
We introduce the Read-Write-Coding-System (RWC) a very flexible class of linear block codes that generate efficient and flexible erasure codes for storage networks. In particular, given a message x of k symbols and a codeword y of n symbols, an RW code defines additional parameters k ≤ r,w ≤ n that offer enhanced possibilities to adjust the fault-tolerance capability of the code. More precisely, an RWC provides linear $\left(n,k,d\right)$-codes that have (a) minimum distance d=n-r+1 for any two codewords, and (b) for each codeword there exists a codeword for each other message with distance of at most w. Furthermore, depending on the values r,w and the code alphabet, different block codes such as parity codes (e.g. RAID 4/5) or Reed-Solomon (RS) codes (if r=k and thus, w=n) can be generated. In storage networks in which I/O accesses are very costly and redundancy is crucial, this flexibility has considerable advantages as r and w can optimally be adapted to read or write intensive applications; only w symbols must be updated if the message x changes completely, what is different from other codes which always need to rewrite y completely as x changes. In this paper, we first state a tight lower bound and basic conditions for all RW codes. Furthermore, we introduce special RW codes in which all mentioned parameters are adjustable even online, that is, those RW codes are adaptive to changing demands. At last, we point out some useful properties regarding safety and security of the stored data.

A Model of Symmetry Breaking in Collective Decision-Making - Hamann, Heiko; Meyer, Bernd; Schmickl, Thomas; Crailsheim, Karl (From Animals to Animats 11)

Robust Undetectable Interference Watermarks - Grza̧ślewicz, Ryszard; Kutyłowski, Jarosław; Kutyłowski, Mirosław; Pietkiewicz, Wojciech (ICCSA'05: Proceedings of the 2005 international conference on Computational Science and Its Applications)

Bregman Clustering for Separable Instances - Ackermann, Marcel R.; Blömer, Johannes (SWAT 2010)

Designing Self-healing in Automotive Systems - Seebach, Hella; Nafz, Florian; Holtmann, Jörg; Meyer, Jan; Tichy, Matthias; Reif, Wolfgang; Schäfer, Wilhelm (Lecture Notes in Computer Science)
Self-healing promises to improve the dependability of systems. In particular safety-critical systems like automotive systems are well suited application, since safe operation is required in these systems even in case of failures. Prerequisite for the improved dependability is the correct realization of the self-healing techniques. Consequently, self-healing activities should be rigorously specified and appropriately integrated with the rest of the system. In this paper, we present an approach for designing self-healing mechanisms in automotive systems. The approach contains a construction model which consist of a structural description as well as an extensive set of constraints. The constraints specify a correct system structure and are also used in the self-healing activities. We exemplify the self-healing approach using the adaptive cruise control system of modern cars.

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing - Briest, Patrick; Chalermsook, Parinya; Khanna, Sanjeev; Laekhanukit, Bundit; Nanongkai, Danupon (Workshop on Internet and Network Economics (WINE))

Preprocessed Global Visibility for Real-Time Rendering on Low-End Hardware - Eikel, Benjamin; Jähn, Claudius; Fischer, Matthias (Advances in Visual Computing)
We present an approach for real-time rendering of complex 3D scenes consisting of millions of polygons on limited graphics hardware. In a preprocessing step, powerful hardware is used to gain fine granular global visibility information of a scene using an adaptive sampling algorithm. Additively the visual influence of each object on the eventual rendered image is estimated. This influence is used to select the most important objects to display in our approximative culling algorithm. After the visibility data is compressed to meet the storage capabilities of small devices, we achieve an interactive walkthrough of the Power Plant scene on a standard netbook with an integrated graphics chipset.

Searchable Compression of Office Documents by XML Schema Subtraction - Böttcher, Stefan; Hartel, Rita; Messinger, Christian (Database and XML Technologies - 7th International XML Database Symposium, XSym 2010)

A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots - Degener, Bastian; Kempkes, Barbara; Kling, Peter; Meyer auf der Heide, Friedhelm (Structural Information and Communication Complexity)

Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II.

Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I.

Towards a Systematic Approach for Capturing Knowledge-Intensive Business Processes - Trier, Matthias; Müller, Claudia (Practical Aspects of Knowledge Management)

Complexity and Approximation of a Geometric Local Robot Assignment Problem - Bonorden, Olaf; Degener, Bastian; Kempkes, Barbara; Pietrzyk, Peter (Algorithmic Aspects of Wireless Sensor Networks)
We introduce a geometric multi-robot assignment problem. Robots positioned in a Euclidean space have to be assigned to treasures in such a way that their joint strength is sufficient to unearth a treasure with a given weight. The robots have a limited range and thus can only be assigned to treasures in their proximity. The objective is to unearth as many treasures as possible. We investigate the complexity of several variants of this problem and show whether they are in $\classP$ or are $\classNP$-complete. Furthermore, we provide a distributed and local constant-factor approximation algorithm using constant-factor resource augmentation for the two-dimensional setting with $\bigO(\log^*n)$ communication rounds.

Reinforcement Learning for Blackjack - Kakvi, Saqib (Lecture Notes in Computer Science)

Three-Valued Spotlight Abstractions - Schrieb, Jonas; Wehrheim, Heike; Wonisch, Daniel (FM 2009: Formal Methods)

On Stackelberg Pricing with Computationally Bounded Consumers - Briest, Patrick; Hoefer, Martin; Gualà, Luciano; Ventre, Carmine (Lecture Notes in Computer Science)
In a Stackelberg pricing game a leader aims to set prices on a subset of a given collection of items, such as to maximize her revenue from a follower purchasing a feasible subset of the items. We focus on the case of computationally bounded followers who cannot optimize exactly over the range of all feasible subsets, but apply some publicly known algorithm to determine the set of items to purchase. This corresponds to general multi-dimensional pricing assuming that consumers cannot optimize over the full domain of their valuation functions but still aim to act rationally to the best of their ability. We consider two versions of this novel type of Stackelberg pricing games. Assuming that items are weighted objects and the follower seeks to purchase a min-cost selection of objects of some minimum weight (the Min-Knapsack problem) and uses a simple greedy 2-approximate algorithm, we show how an extension of the known single-price algorithm can be used to derive a polynomial-time (2 + ε)-approximation algorithm for the leader’s revenue maximization problem based on so-called near-uniform price assignments. We also prove the problem to be strongly NP-hard. Considering the case that items are subsets of some ground set which the follower seeks to cover (the Set-Cover problem) via a standard primal-dual approach, we prove that near-uniform price assignments fail to yield a good approximation guarantee. However, in the special case of elements with frequency 2 (the Vertex-Cover problem) it turns out that exact revenue maximization can be done in polynomial-time. This stands in sharp contrast to the fact that revenue maximization becomes APX-hard already for elements with frequency 3.

Creating Butterflies in the Core – A Network Coding Extension for MPLS/RSVP-TE - Biermann, Thorsten; Schwabe, Arne; Karl, Holger (NETWORKING 2009)

Reinforcement Learning for Blackjack - Kakvi, Saqib (Lecture Notes in Computer Science)

Uniform Budgets and the Envy-Free Pricing Problem - Briest, Patrick (Proceedings of the 35th InternationalColloquium on Automata, Languages and Programming (ICALP))

The Kinetic Facility Location Problem - Degener, Bastian; Gehweiler, Joachim; Lammersen, Christiane (Proceedings of the 11th Scandinavian Workshop on Algorithm Theory (SWAT))

Aggregating Robots Compute: An Adaptive Heuristic for the Euclidean Steiner Tree Problem - Hamann, Heiko; Wörn, Heinz (The tenth International Conference on Simulation of Adaptive Behavior (SAB'08))

On Faster Integer Calculations Using Non-arithmetic Primitives - Lürwer-Brüggemeier, Katharina; Ziegler, Martin (Unconventional Computing)

The k-Resource Problem on Uniform and on Uniformly Decomposable Metric Spaces - Bienkowski, Marcin; Kutyłowski, Jarosław (Lecture Notes in Computer Science)
We define a natural generalization of the prominent k-server problem, the k-resource problem. It occurs in metric spaces with some demands and resources given at its points. The demands may vary with time, but the total demand may never exceed k. The goal of an online algorithm is to satisfy demands by moving resources, while minimizing the cost for transporting resources. We give an asymptotically optimal O(log(min {n,k}))-competitive randomized algorithm and an O(min {k,n})-competitive deterministic one for the k-resource problem on uniform metric spaces consisting of n points. This extends known results for paging to the more general setting of k-resource. Basing on the results for uniform metric spaces, we develop a randomized algorithm solving the k-resource and the k-server problem on metric spaces which can be decomposed into components far away from each other. The algorithm achieves a competitive ratio of O(log(min {n,k})), provided that it has some extra resources more than the optimal algorithm.

Cryptanalysis of Unbalanced RSA with Small CRT-Exponent - May, Alexander (Advances in Cryptology — CRYPTO 2002)

Low Secret Exponent RSA Revisited - Blömer, Johannes; May, Alexander (Lecture Notes in Computer Science)

Key Revocation with Interval Cover Families - Blömer, Johannes; May, Alexander (Selected Areas in Cryptography)

Dimension Reduction Methods for Convolution Modular Lattices - May, Alexander; Silverman, Joseph H. (Lecture Notes in Computer Science)

A Probabilistic Zero-Test for Expressions Involving Roots of Rational Numbers - Blömer, Johannes (Algorithms — ESA’ 98)

Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs - Dynia, Miroslaw; Korzeniowski, Miroslaw; Kutyłowski, Jarosław (Proc. of the 33rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07))

(Short) Survey of Real Hypercomputation - Ziegler, Martin (Lecture Notes in Computer Science)

Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation - Meer, Klaus; Ziegler, Martin (Mathematical Foundations of Computer Science 2007)

Upper Bounds on the Bisection Width of 3- and 4-Regular Graphs - Monien, Burkhard; Preis, Robert (Mathematical Foundations of Computer Science 2001)

Evaluating XPath Queries on XML Data Streams - Böttcher, Stefan; Steinmetz, Rita (Data Management. Data, Data Everywhere, 24th British National Conference on Databases, BNCOD 24)

Data Management for Mobile Ajax Web 2.0 Applications - Böttcher, Stefan; Steinmetz, Rita (Database and Expert Systems Applications, 18th International Conference, DEXA 2007)

Online Multi-path Routing in a Maze - Rührup, Stefan; Schindelhauer, Christian (Proc. of the 17th International Symposium on Algorithms and Computation (ISAAC 2006))

Reliable Broadcasting Without Collision Detection - Kutyłowski, Jarosław; Zagórski, Filip (SOFSEM 2006: Theory and Practice of Computer Science)
We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways. Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure. We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions. Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.

Fault Based Collision Attacks on AES - Blömer, Johannes; Krummel, Volker (Lecture Notes in Computer Science)

Wagner’s Attack on a Secure CRT-RSA Algorithm Reconsidered - Blömer, Johannes; Otto, Martin (Lecture Notes in Computer Science)

Sign Change Fault Attacks on Elliptic Curve Cryptosystems - Blömer, Johannes; Otto, Martin; Seifert, Jean-Pierre (Lecture Notes in Computer Science)

Power-Aware Collective Tree Exploration - Dynia, Miroslaw; Korzeniowski, Miroslaw; Schindelhauer, Christian (Architecture of Computing Systems - ARCS)

Uncomputability Below the Real Halting Problem - Meer, Klaus; Ziegler, Martin (Logical Approaches to Computational Barriers)

De Dictionariis Dynamicis Pauco Spatio Utentibus ({lat.} On Dynamic Dictionaries Using Little Space) - Demaine, Erik D.; Meyer auf der Heide, Friedhelm; Pagh, Rasmus; Pǎtraşcu, Mihai (LATIN 2006: Theoretical Informatics)

Smart Robot Teams Exploring Sparse Trees - Dynia, M.; Kutyłowski, J.; Meyer auf der Heide, Friedhelm; Schindelhauer, Christian (Lecture Notes in Computer Science)

DTD-Driven Structure Preserving XML Compression - Böttcher, Stefan; Steinmetz, Rita (Flexible and Efficient Information Handling, 23rd British National Conference on Databases, BNCOD 23)

Information Disclosure by XPath Queries - Böttcher, Stefan; Steinmetz, Rita (Secure Data Management, Third VLDB Workshop, SDM 2006)

Cohen–Lenstra Heuristics of Quadratic Number Fields - Fouvry, Étienne; Klüners, Jürgen (Lecture Notes in Computer Science)
We establish a link between some heuristic asymptotic formulas (due to Cohen and Lenstra) concerning the moments of the p–part of the class groups of quadratic fields and formulas giving the frequency of the values of the p–rank of these class groups.

A Simpler Sieving Device: Combining ECM and TWIRL - Geiselmann, Willi; Januszewski, Fabian; Köpfer, Hubert; Pelzl, Jan; Steinwandt, Rainer (Information Security and Cryptology – ICISC 2006)

Performance Analysis of the Hierarchical Layer Graph for Wireless Networks - Rührup, Stefan; Schindelhauer, Christian; Volbert, Klaus (Proc. of 4th International Conference on Ad-Hoc, Mobile & Wireless Networks (ADHOC-NOW 2005))
The Hierarchical Layer Graph (HL graph) is a promising network topology for wireless networks with variable transmission ranges. It was introduced and analyzed by Meyer auf der Heide et al. 2004. In this paper we present a distributed, localized and resource-efficient algorithm for constructing this graph. The qualtiy of the HL graph depends on the domination radius and the publication radius, which affect the amount of interference in the network. These parameters also determine whether the HL graph is a c-spanner, which implies an energy-efficient topology. We investigate the performance on randomly distributed node sets and show that the restrictions on these parameters derived from a worst case analysis are not so tight using realistic settings. Here, we present the results of our extensive experimental evaluation, measuring congestion, dilation and energy. Congestion includes the load that is induced by interfering edges. We distinguish between congestion and realistic congestion where we also take the signal-to-interference ratio into account. Our experiments show that the HL graph contains energy-efficient paths as well as paths with a few number of hops while preserving a low congestion.

Probability Distributions for Channel Utilisation - Schindelhauer, Christian; Voß, Kerstin (Proc. of 4th International Conference on Ad-Hoc Networks & Wireless (ADHOC-NOW 2005))

Content Distribution in Heterogenous Video-on-Demand P2P Networks with ARIMA Forecasts - Loeser, Chris; Schomaker, Gunnar; Brinkmann, André; Vodisek, Mario; Heidebuer, Michael (Proceedings of the 4th International Conference on Networking)

A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers - Blömer, Johannes; May, Alexander (EUROCRYPT 2005)

Partial Key Exposure Attacks on RSA up to Full Size Exponents - Ernst, Matthias; Jochemsz, Ellen; May, Alexander; de Weger, Benne (EUROCRYPT 2005)

Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio - Rührup, Stefan; Schindelhauer, Christian (Algorithms – ESA 2005)

Mischbauweise sorgt für frischen Wind - Meschut, Gerson (Konstruktion)

Facility Location in Sublinear Time - Bădoiu, Mihai; Czumaj, Artur; Indyk, Piotr; Sohler, Christian (Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP))

Online Occlusion Culling - Frahling, Gereon; Krokowski, Jens (Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005))
Modern computer graphics systems are able to render sophisticated 3D szenes consisting of millions of polygons. In this paper we address the problem of occlusion culling. Aila, Miettinen, and Nordlund suggested to implement a FIFO buffer on graphics cards which is able to delay the polygons before drawing them. When one of the polygons within the buffer is occluded or masked by another polygon arriving later from the application, the rendering engine can drop the occluded one without rendering, saving important rendering time. We introduce a theoretical online model to analyse these problems in theory using competitive analysis. For different cost measures addressed we invent the first competitive algorithms for online occlusion culling. Our implementation shows that these algorithms outperform known ones for real 3D scenes as well.

Dynamic Page Migration Under Brownian Motion - Bienkowski, Marcin; Korzeniowski, Miroslaw (Proc. of the European Conference in Parallel Processing (Euro-Par))
We consider Dynamic Page Migration (DPM) problem, one of the fundamental subproblems of data management in dynamically changing networks. We investigate a hybrid scenario, where access patterns to the shared object are dictated by an adversary, and each processor performs a random walk in X. We extend the previous results of [4]: we develop algorithms for the case where X is a ring, and prove that with high probability they achieve a competitive ratio of O~(min{D−−√4,n}), where D is the size of the shared object and n is the number of nodes in the network. These results hold also for any d-dimensional torus or mesh with diameter at least Ω~(D−−√).

Bucket Game with Applications to Set Multicover and Dynamic Page Migration - Bienkowski, Marcin; Byrka, Jarosław (Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005))
We present a simple two-person Bucket Game, based on throwing balls into buckets, and we discuss possible players' strategies. We use these strategies to create an approximation algorithm for a generalization of the well known Set Cover problem, where we need to cover each element by at least $k$ sets. Furthermore, we apply these strategies to construct a randomized algorithm for Dynamic Page Migration problem achieving the optimal competitive ratio against an oblivious adversary.

Cube Connected Cycles Based Bluetooth Scatternet Formation - Bienkowski, Marcin; Brinkmann, André; Korzeniowski, Miroslaw; Orhan, Orhan (Proceedings of the 4th International Conference on Networking)
Bluetooth is a wireless communication standard developed for personal area networks (PAN) that gained popularity in the last years. It was designed to connect a few devices together, however nowadays there is a need to build larger networks. Construction and maintenance algorithms have great effect on performance of the network. We present an algorithm based on Cube Connected Cycles (CCC) topology and show how to maintain the network so that it is easily scalable. Our design guarantees good properties such as constant degree and logarithmic dilation. Besides, the construction costs are proven to be at most constant times larger than any other algorithm would need.

Improved Algorithms for Dynamic Page Migration - Bienkowski, Marcin; Dynia, Miroslaw; Korzeniowski, Miroslaw (Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS))
The dynamic page migration problem citedynamic-page-migration is defined in a distributed network of $n$ mobile nodes sharing one indivisible memory page of size $D$. During runtime, the nodes can both access a unit of data from the page and move with a constant speed, thus changing the costs of communication. The problem is to compute online a schedule of page movements to minimize the total communication cost. In this paper we construct and analyze the first deterministic algorithm for this problem. We prove that it achieves an (up to a constant factor) optimal competitive ratio $O(n cdot sqrtD)$. We show that the randomization of this algorithm improves this ratio to $O(sqrtD cdot log n)$ (against an oblivious adversary). This substantially improves an $O(n cdot sqrtD)$ upper bound from citedynamic-page-migration. We also give an almost matching lower bound of $Omega(sqrtD cdot sqrtlog n)$ for this problem.

On Approximating Real-World Halting Problems - Köhler, Sven; Schindelhauer, Christian; Ziegler, Martin (Fundamentals of Computation Theory)

An Explicit Solution to Post’s Problem over the Reals - Meer, Klaus; Ziegler, Martin (Fundamentals of Computation Theory)

Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism - Ziegler, Martin (Proc. CiE 2005: New Computational Paradigms)
The sometimes so-called Main Theorem of Recursive Analysis implies that any computable real function is necessarily continuous. We consider three relaxations of this common notion of real computability for the purpose of treating also discontinuous functions f:R->R: *) non-deterministic computation; *) relativized computation, specifically given access to oracles like 0' or 0''; *) encoding input x and/or output y=f(x) in weaker ways according to the Real Arithmetic Hierarchy. It turns out that, among these approaches, only the first one provides the required power.

Dynamic Load Balancing in Distributed Hash Tables - Bienkowski, Marcin; Korzeniowski, Miroslaw; Meyer auf der Heide, Friedhelm (Peer-to-Peer Systems IV)

Page Migration in Dynamic Networks - Bienkowski, Marcin; Meyer auf der Heide, Friedhelm (Mathematical Foundations of Computer Science 2005)

A Web Computing Environment for Parallel Algorithms in Java - Bonorden, Olaf; Gehweiler, Joachim; Meyer auf der Heide, Friedhelm (Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM))
We present a web computing library (PUBWCL) in Java that allows to execute strongly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library.

Load Balancing Strategies in a Web Computing Environment - Bonorden, Olaf; Gehweiler, Joachim; Meyer auf der Heide, Friedhelm (Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM))
We compare different load balancing strategies for Bulk-Synchronous Parallel (BSP) programs in a web computing environment. In order to handle the influence of the fluctuating available computation power, we classify the external work load. We evaluate the load balancing algorithms using our web computing library for BSP programs in Java (PUBWCL). Thereby we simulated the external work load in order to have repeatable testing conditions. With the best performing load balancing strategy we could save 39% of the execution time averaged and even up to 50% in particular cases.

Detecting Privacy Violations in Sensitive XML Databases - Böttcher, Stefan; Steinmetz, Rita (Secure Data Management, Second VLDB Workshop, SDM 2005)

The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes - Briest, Patrick; Brockhoff, Dimo; Degener, Bastian; Englert, Matthias; Gunia, Christian; Heering, Oliver; Jansen, Thomas; Leifhelm, Michael; Plociennik, Kai; Röglin, Heiko; Schweer, Andrea; Sudholt, Dirk; et al. (Parallel Problem Solving from Nature - PPSN VIII)

Provably Secure Masking of AES - Blömer, Johannes; Guajardo, Jorge; Krummel, Volker (Selected Areas in Cryptography)

A Generalized Wiener Attack on RSA - Blömer, Johannes; May, Alexander (Public Key Cryptography – PKC 2004)

Secret Exponent Attacks on RSA-type Schemes with Moduli N=p^{r}q - May, Alexander (Public Key Cryptography – PKC 2004)

Computing the RSA Secret Key Is Deterministic Polynomial Time Equivalent to Factoring - May, Alexander (Advances in Cryptology – CRYPTO 2004)

Extreme Points Under Random Noise - Damerow, Valentina; Sohler, Christian (Proceedings of the 12th European Symposium on Algorithms (ESA'04))
Given a point set P in the d-dimensional unit hypercube, we give upper bounds on the maximal expected number of extreme points when each point is perturbed by small random noise chosen independently for each point from the same noise distribution Δ. Our results are parametrized by the variance of the noise distribution. For large variance we essentially consider the average case for distribution Δ while for variance 0 we consider the worst case. Hence our results give upper bounds on the number of extreme points where our input distributions range from average case to worst case. Our main contribution is a rather general lemma that can be used to obtain upper bounds on the expected number of extreme points for a large class of noise distributions. We then apply this lemma to obtain explicit bounds for random noise coming from the Gaussian normal distribution of variance σ² and the uniform distribution in a hypercube of side length &epsilon. For these noise distributions we show upper bounds of O( (1/ σ )^d * log^3/2 * d - 1 n ) and O( ( (n log n) / ε )^d/(d+1) ), respectively. Besides its theoretical motivation our model is also motivated by the observation that in many applications of convex hull algorithms the input data is inherently noisy, e.g. when the data comes from physical measurement or imprecise arithmetic is used.

Fast Multipoint Evaluation of Bivariate Polynomials - Nüsken, Michael; Ziegler, Martin (Proc. 12th Annual Symposium on Algorithms (ESA'04))
We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n^2 coefficients, simultaneously at n^2 given points using a total of O(n^2.667) arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of O(N^0.334) per point.

Spanners, Weak Spanners, and Power Spanners for Wireless Networks - Schindelhauer, Christian; Volbert, Klaus; Ziegler, Martin (Proc. of 15th Annual International Symposium on Algorithms and Computation (ISAAC'04))
For $c in REAL$, a $c$-spanner is a subgraph of a complete Euclidean graph satisfying that between any two vertices there exists a path of weighted length at most $c$ times their geometric distance. Based on this property to approximate a complete weighted graph, sparse spanners have found many applications, e.g., in FPTAS, geometric searching, and radio networks. For geometric searching, it turned out to suffice whether the radius rather than the length of some path between any two vertices is bounded relatively to their geometric distance; this is the defining property of weak spanners. Finally regarding radio network applications, a power spanner accounts for the total energy afforded for a wireless transmission with the requirement that the sum of the squares of the lengths of some path between any two planar vertices must be bounded relatively to the square of their geometric distance (or higher powers up to 6 or even 8). While it is known that any $c$-spanner is also both a weak $C_1$-spanner and a $C_2$-power spanner (for appropriate $C_1,C_2$ depending only on $c$ but not on the graph under consideration), we show that the converse fails: There exists a family of $c_1$-power spanners that are no weak $C$-spanners and also a family of weak $c_2$-spanners that are no $C$-spanners for any fixed $C$ (and thus no uniform spanners, either). However the deepest result of the present work reveals that, surprisingly, any weak spanner is also a uniform power spanner. We further generalize the latter notion by considering $(c,delta)$-power spanners where the sum of the $delta$-th powers of the lengths has to be bounded; so $(cdot,2)$-power spanners coincide with the usual power spanners and $(cdot,1)$-power spanners are classical spanners. Interestingly, these $(cdot,delta)$-power spanners form a strict hierarchy where the above results still hold for any $deltageq2$; some even hold for $delta>1$ while counterexamples reveal others to fail for $delta<2$. In fact we show that in general every self-similar curve of fractal dimension $d>delta$ is no $(C,delta)$-power spanner for any fixed $C$.

Labeling Smart Dust - Bansal, Vikas; Meyer auf der Heide, Friedhelm; Sohler, Christian (12th Annual European Symposium on Algorithms (ESA 2004))
Given n distinct points p1, p2, ... , pn in the plane, the map labeling problem with four squares is to place n axis-parallel equi-sized squares Q1, ... ,Qn of maximum possible size such that pi is a corner of Qi and no two squares overlap. This problem is NP-hard and no algorithm with approximation ratio better than 1/2 exists unless P = NP [10]. In this paper, we consider a scenario where we want to visualize the information gathered by smart dust, i.e. by a large set of simple devices, each consisting of a sensor and a sender that can gather sensor data and send it to a central station. Our task is to label (the positions of) these sensors in a way described by the labeling problem above. Since these devices are not positioned accurately (for example, they might be dropped from an airplane), this gives rise to consider the map labeling problem under the assumption, that the positions of the points are not fixed precisely, but perturbed by random noise. In other words, we consider the smoothed complexity of the map labeling problem. We present an algorithm that, under such an assumption and Gaussian random noise with sufficiently large variance, has linear smoothed complexity.

A Runtime Environment for Reconfigurable Hardware Operating Systems - Walder, Herbert; Platzner, Marco (Proceedings of the 14th International Conference on Field Programmable Logic and Applications (FPL))

Algorithmic Approaches for Storage Networks - Salzwedel, Kay A. (Algorithms for Memory Hierarchies)

New Partial Key Exposure Attacks on RSA - Blömer, Johannes; May, Alexander (Advances in Cryptology - CRYPTO 2003)