@inbook{3006, author = {{Blömer, Johannes and May, Alexander}}, booktitle = {{EUROCRYPT 2005}}, isbn = {{9783540259107}}, issn = {{0302-9743}}, pages = {{251--267}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{A Tool Kit for Finding Small Roots of Bivariate Polynomials over the Integers}}}, doi = {{10.1007/11426639_15}}, year = {{2005}}, } @inbook{3010, author = {{Ernst, Matthias and Jochemsz, Ellen and May, Alexander and de Weger, Benne}}, booktitle = {{EUROCRYPT 2005}}, isbn = {{9783540259107}}, issn = {{0302-9743}}, pages = {{371--386}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Partial Key Exposure Attacks on RSA up to Full Size Exponents}}}, doi = {{10.1007/11426639_22}}, year = {{2005}}, } @inbook{26991, author = {{Rührup, Stefan and Schindelhauer, Christian}}, booktitle = {{Algorithms – ESA 2005}}, issn = {{0302-9743}}, title = {{{Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio}}}, doi = {{10.1007/11561071_5}}, year = {{2005}}, } @inproceedings{18768, author = {{Bădoiu, Mihai and Czumaj, Artur and Indyk, Piotr and Sohler, Christian}}, booktitle = {{Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)}}, isbn = {{9783540275800}}, issn = {{0302-9743}}, pages = {{866--877}}, title = {{{Facility Location in Sublinear Time}}}, doi = {{10.1007/11523468_70}}, year = {{2005}}, } @inproceedings{18867, abstract = {{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.}}, author = {{Frahling, Gereon and Krokowski, Jens}}, booktitle = {{Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)}}, isbn = {{9783540291183}}, issn = {{0302-9743}}, pages = {{758--769}}, publisher = {{Springer}}, title = {{{Online Occlusion Culling}}}, doi = {{10.1007/11561071_67}}, volume = {{3669}}, year = {{2005}}, } @inproceedings{18912, abstract = {{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−−√).}}, author = {{Bienkowski, Marcin and Korzeniowski, Miroslaw}}, booktitle = {{Proc. of the European Conference in Parallel Processing (Euro-Par)}}, isbn = {{9783540287001}}, issn = {{0302-9743}}, title = {{{Dynamic Page Migration Under Brownian Motion}}}, doi = {{10.1007/11549468_105}}, year = {{2005}}, } @inproceedings{18915, abstract = {{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.}}, author = {{Bienkowski, Marcin and Byrka, Jarosław}}, booktitle = {{Proc. of the 13th Annual European Symposium on Algorithms (ESA 2005)}}, isbn = {{9783540291183}}, issn = {{0302-9743}}, pages = {{815--826}}, publisher = {{Springer }}, title = {{{Bucket Game with Applications to Set Multicover and Dynamic Page Migration}}}, doi = {{10.1007/11561071_72}}, volume = {{3669}}, year = {{2005}}, } @inproceedings{18924, abstract = {{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.}}, author = {{Bienkowski, Marcin and Brinkmann, André and Korzeniowski, Miroslaw and Orhan, Orhan}}, booktitle = {{Proceedings of the 4th International Conference on Networking}}, isbn = {{9783540253396}}, issn = {{0302-9743}}, pages = {{413--420}}, publisher = {{Springer}}, title = {{{Cube Connected Cycles Based Bluetooth Scatternet Formation}}}, doi = {{10.1007/978-3-540-31956-6_49}}, volume = {{3420}}, year = {{2005}}, } @inproceedings{18925, abstract = {{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.}}, author = {{Bienkowski, Marcin and Dynia, Miroslaw and Korzeniowski, Miroslaw}}, booktitle = {{Proc. of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS)}}, isbn = {{9783540249986}}, issn = {{0302-9743}}, pages = {{365--376}}, title = {{{Improved Algorithms for Dynamic Page Migration}}}, doi = {{10.1007/978-3-540-31856-9_30}}, year = {{2005}}, } @inbook{17988, author = {{Köhler, Sven and Schindelhauer, Christian and Ziegler, Martin}}, booktitle = {{Fundamentals of Computation Theory}}, isbn = {{9783540281931}}, issn = {{0302-9743}}, title = {{{On Approximating Real-World Halting Problems}}}, doi = {{10.1007/11537311_40}}, year = {{2005}}, } @inbook{17989, author = {{Meer, Klaus and Ziegler, Martin}}, booktitle = {{Fundamentals of Computation Theory}}, isbn = {{9783540281931}}, issn = {{0302-9743}}, title = {{{An Explicit Solution to Post’s Problem over the Reals}}}, doi = {{10.1007/11537311_41}}, year = {{2005}}, } @inproceedings{18280, abstract = {{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.}}, author = {{Ziegler, Martin}}, booktitle = {{Proc. CiE 2005: New Computational Paradigms}}, isbn = {{9783540261797}}, issn = {{0302-9743}}, pages = {{562--571}}, publisher = {{Springer}}, title = {{{Computability and Continuity on the Real Arithmetic Hierarchy and the Power of Type-2 Nondeterminism}}}, doi = {{10.1007/11494645_68}}, volume = {{3526}}, year = {{2005}}, } @inbook{16468, author = {{Bienkowski, Marcin and Korzeniowski, Miroslaw and Meyer auf der Heide, Friedhelm}}, booktitle = {{Peer-to-Peer Systems IV}}, isbn = {{9783540290681}}, issn = {{0302-9743}}, title = {{{Dynamic Load Balancing in Distributed Hash Tables}}}, doi = {{10.1007/11558989_20}}, year = {{2005}}, } @inbook{16469, author = {{Bienkowski, Marcin and Meyer auf der Heide, Friedhelm}}, booktitle = {{Mathematical Foundations of Computer Science 2005}}, isbn = {{9783540287025}}, issn = {{0302-9743}}, title = {{{Page Migration in Dynamic Networks}}}, doi = {{10.1007/11549345_1}}, year = {{2005}}, } @inproceedings{16470, abstract = {{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. }}, author = {{Bonorden, Olaf and Gehweiler, Joachim and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM)}}, isbn = {{9783540341413}}, issn = {{0302-9743}}, pages = {{801--808}}, title = {{{A Web Computing Environment for Parallel Algorithms in Java}}}, doi = {{10.1007/11752578_96}}, year = {{2005}}, } @inproceedings{16471, abstract = {{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.}}, author = {{Bonorden, Olaf and Gehweiler, Joachim and Meyer auf der Heide, Friedhelm}}, booktitle = {{Proceeedings of 6th International Conference on Parallel Processing and Applied Mathematics (PPAM)}}, isbn = {{9783540341413}}, issn = {{0302-9743}}, pages = {{839--846}}, title = {{{Load Balancing Strategies in a Web Computing Environment}}}, doi = {{10.1007/11752578_101}}, year = {{2005}}, } @inproceedings{15156, author = {{Böttcher, Stefan and Steinmetz, Rita}}, booktitle = {{Secure Data Management, Second VLDB Workshop, SDM 2005}}, isbn = {{9783540287988}}, issn = {{0302-9743}}, pages = {{143--154}}, publisher = {{Springer}}, title = {{{Detecting Privacy Violations in Sensitive XML Databases}}}, doi = {{10.1007/11552338_10}}, year = {{2005}}, } @inproceedings{66533, author = {{Hund, Marcus and Mertsching, Bärbel}}, booktitle = {{10th Ibero-American Congress on Pattern Recognition (XCIARP)}}, isbn = {{9783540298502}}, issn = {{0302-9743}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{A Computational Approach to Illusory Contour Perception Based on the Tensor Voting Technique}}}, doi = {{10.1007/11578079_8}}, year = {{2005}}, } @inproceedings{19692, author = {{Briest, Patrick and Brockhoff, Dimo and Degener, Bastian and Englert, Matthias and Gunia, Christian and Heering, Oliver and Jansen, Thomas and Leifhelm, Michael and Plociennik, Kai and Röglin, Heiko and Schweer, Andrea and Sudholt, Dirk and Tannenbaum, Stefan and Wegener, Ingo}}, booktitle = {{Parallel Problem Solving from Nature - PPSN VIII}}, isbn = {{9783540230922}}, issn = {{0302-9743}}, title = {{{The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes}}}, doi = {{10.1007/978-3-540-30217-9_4}}, year = {{2004}}, } @inbook{3011, author = {{Blömer, Johannes and Guajardo, Jorge and Krummel, Volker}}, booktitle = {{Selected Areas in Cryptography}}, isbn = {{9783540243274}}, issn = {{0302-9743}}, pages = {{69--83}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Provably Secure Masking of AES}}}, doi = {{10.1007/978-3-540-30564-4_5}}, year = {{2004}}, }