@inproceedings{15150, author = {{Böttcher, Stefan and Steinmetz, Rita}}, booktitle = {{Flexible and Efficient Information Handling, 23rd British National Conference on Databases, BNCOD 23}}, isbn = {{9783540359692}}, issn = {{0302-9743}}, pages = {{266--269}}, title = {{{DTD-Driven Structure Preserving XML Compression}}}, doi = {{10.1007/11788911_27}}, year = {{2006}}, } @inproceedings{15152, author = {{Böttcher, Stefan and Steinmetz, Rita}}, booktitle = {{Secure Data Management, Third VLDB Workshop, SDM 2006}}, isbn = {{9783540389842}}, issn = {{0302-9743}}, pages = {{160--174}}, publisher = {{Springer}}, title = {{{Information Disclosure by XPath Queries}}}, doi = {{10.1007/11844662_12}}, year = {{2006}}, } @inbook{53181, author = {{Geiselmann, Willi and Januszewski, Fabian and Köpfer, Hubert and Pelzl, Jan and Steinwandt, Rainer}}, booktitle = {{Information Security and Cryptology – ICISC 2006}}, isbn = {{9783540491125}}, issn = {{0302-9743}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{A Simpler Sieving Device: Combining ECM and TWIRL}}}, doi = {{10.1007/11927587_12}}, year = {{2006}}, } @inbook{35958, abstract = {{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.}}, author = {{Fouvry, Étienne and Klüners, Jürgen}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540360759}}, issn = {{0302-9743}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Cohen–Lenstra Heuristics of Quadratic Number Fields}}}, doi = {{10.1007/11792086_4}}, year = {{2006}}, } @inproceedings{19835, abstract = {{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.}}, author = {{Rührup, Stefan and Schindelhauer, Christian and Volbert, Klaus}}, booktitle = {{Proc. of 4th International Conference on Ad-Hoc, Mobile & Wireless Networks (ADHOC-NOW 2005)}}, isbn = {{9783540291329}}, issn = {{0302-9743}}, pages = {{244--257}}, title = {{{Performance Analysis of the Hierarchical Layer Graph for Wireless Networks}}}, doi = {{10.1007/11561354_21}}, volume = {{3738}}, year = {{2005}}, } @inbook{19836, author = {{Schindelhauer, Christian and Voß, Kerstin}}, booktitle = {{Proc. of 4th International Conference on Ad-Hoc Networks & Wireless (ADHOC-NOW 2005)}}, isbn = {{9783540291329}}, issn = {{0302-9743}}, pages = {{271--284}}, title = {{{Probability Distributions for Channel Utilisation}}}, doi = {{10.1007/11561354_23}}, year = {{2005}}, } @inproceedings{19912, author = {{Loeser, Chris and Schomaker, Gunnar and Brinkmann, André and Vodisek, Mario and Heidebuer, Michael}}, booktitle = {{Proceedings of the 4th International Conference on Networking}}, isbn = {{9783540253389}}, issn = {{0302-9743}}, pages = {{800--810}}, title = {{{Content Distribution in Heterogenous Video-on-Demand P2P Networks with ARIMA Forecasts}}}, doi = {{10.1007/978-3-540-31957-3_90}}, volume = {{3421}}, year = {{2005}}, } @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}}, }