@inbook{3018, author = {{Blömer, Johannes and Seifert, Jean-Pierre}}, booktitle = {{Financial Cryptography}}, isbn = {{9783540406631}}, issn = {{0302-9743}}, pages = {{162--181}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Fault Based Cryptanalysis of the Advanced Encryption Standard (AES)}}}, doi = {{10.1007/978-3-540-45126-6_12}}, year = {{2003}}, } @inproceedings{18196, abstract = {{Fast algorithms for arithmetic on real or complex polynomials are well-known and have proven to be not only asymptotically efficient but also very practical. Based on FAST FOURIER TRANSFORM, they for instance multiply two polynomials of degree up to N or multi-evaluate one at N points simultaneously within quasi-linear time O(N polylog N). An extension to (and in fact the mere definition of) polynomials over fields R and C to the SKEW-field H of quaternions is promising but still missing. The present work proposes three approaches which in the commutative case coincide but for H turn out to differ, each one satisfying some desirable properties while lacking others. For each notion, we devise algorithms for according arithmetic; these are quasi-optimal in that their running times match lower complexity bounds up to polylogarithmic factors.}}, author = {{Ziegler, Martin}}, booktitle = {{Proc. 14th Annual International Symposium on Algorithms and Computation (ISAAC'03)}}, isbn = {{9783540206958}}, issn = {{0302-9743}}, pages = {{705--715}}, title = {{{Quasi-optimal Arithmetic for Quaternion Polynomials}}}, doi = {{10.1007/978-3-540-24587-2_72}}, year = {{2003}}, } @inbook{18258, abstract = {{Multi-evaluation of the Coulomb potential induced by N particles is a central part of N-body simulations. In 3D, known subquadratic time algorithms return approximations up to given ABSOLUTE precision. By combining data structures from Computational Geometry with fast polynomial arithmetic, the present work obtains approximations of prescribable RELATIVE error e>0 in time O(1/e*N*polylog N).}}, author = {{Ziegler, Martin}}, booktitle = {{Lecture Notes in Computer Science}}, editor = {{Dehne, F. and Sack, JR. and Smid, M.}}, isbn = {{9783540405450}}, issn = {{0302-9743}}, publisher = {{Springer}}, title = {{{Fast Relative Approximation of Potential Fields}}}, doi = {{10.1007/978-3-540-45078-8_13}}, volume = {{2748}}, year = {{2003}}, } @inbook{16543, author = {{Dellnitz, Michael and Preis, Robert}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540405542}}, issn = {{0302-9743}}, title = {{{Congestion and Almost Invariant Sets in Dynamical Systems}}}, doi = {{10.1007/3-540-45084-x_8}}, year = {{2003}}, } @inbook{16664, author = {{Schütze, Oliver}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540018698}}, issn = {{0302-9743}}, title = {{{A New Data Structure for the Nondominance Problem in Multi-objective Optimization}}}, doi = {{10.1007/3-540-36970-8_36}}, year = {{2003}}, } @inbook{16665, author = {{Schütze, Oliver and Mostaghim, Sanaz and Dellnitz, Michael and Teich, Jürgen}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540018698}}, issn = {{0302-9743}}, title = {{{Covering Pareto Sets by Multilevel Evolutionary Subdivision Techniques}}}, doi = {{10.1007/3-540-36970-8_9}}, year = {{2003}}, } @inproceedings{15077, author = {{Böttcher, Stefan and Steinmetz, Rita}}, booktitle = {{Advances in Databases and Information Systems, 7th East European Conference, ADBIS 2003}}, isbn = {{9783540200475}}, issn = {{0302-9743}}, pages = {{400--410}}, publisher = {{Springer}}, title = {{{Testing Containment of XPath Expressions in Order to Reduce the Data Transfer to Mobile Clients}}}, doi = {{10.1007/978-3-540-39403-7_30}}, year = {{2003}}, } @inproceedings{15078, author = {{Böttcher, Stefan and Steinmetz, Rita}}, booktitle = {{Database and XML Technologies, First International XML Database Symposium, XSym 2003}}, isbn = {{9783540200550}}, issn = {{0302-9743}}, pages = {{85--99}}, title = {{{A DTD Graph Based XPath Query Subsumption Test}}}, doi = {{10.1007/978-3-540-39429-7_6}}, year = {{2003}}, } @inproceedings{13615, author = {{Steiger, Christoph and Walder, Herbert and Platzner, Marco}}, booktitle = {{Proceedings of the 13th International Conference on Field Programmable Logic and Applications (FPL)}}, isbn = {{9783540408222}}, issn = {{0302-9743}}, pages = {{575--584}}, publisher = {{Springer}}, title = {{{Heuristics for Online Scheduling Real-Time Tasks to Partially Reconfigurable Devices}}}, doi = {{10.1007/978-3-540-45234-8_56}}, year = {{2003}}, } @inproceedings{19850, author = {{Wanka, Rolf}}, booktitle = {{Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG)}}, isbn = {{9783540003311}}, issn = {{0302-9743}}, pages = {{413--420}}, title = {{{Any Load-Balancing Regimen for Evolving Tree Computations on Circulant Graphs Is Asymptotically Optimal}}}, doi = {{10.1007/3-540-36379-3_36}}, year = {{2002}}, } @inproceedings{24338, author = {{Grünewald, Matthias and Lukovszki, Tamás and Schindelhauer, Christian and Volbert, Klaus}}, booktitle = {{Proceedings of the 8th International Euro-Par Conference}}, issn = {{0302-9743}}, title = {{{Distributed Maintenance of Resource Efficient Wireless Network Topologies}}}, doi = {{10.1007/3-540-45706-2_134}}, year = {{2002}}, } @inproceedings{18566, abstract = {{We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played in rounds and in each round both the hunter and the rabbit are located at a node of the graph. Between rounds both the hunter and the rabbit can stay at the current node or move to another node. The hunter is assumed to be restricted to the graph G: in every round, the hunter can move using at most one edge. For the rabbit we investigate two models: in one model the rabbit is restricted to the same graph as the hunter, and in the other model the rabbit is unrestricted, i.e., it can jump to an arbitrary node in every round. We say that the rabbit is caught as soon as hunter and rabbit are located at the same node in a round. The goal of the hunter is to catch the rabbit in as few rounds as possible, whereas the rabbit aims to maximize the number of rounds until it is caught. Given a randomized hunter strategy for G, the escape length for that strategy is the worst case expected number of rounds it takes the hunter to catch the rabbit, where the worst case is with regards to all (possibly randomized) rabbit strategies. Our main result is a hunter strategy for general graphs with an escape length of only O (n log (diam(G))) against restricted as well as unrestricted rabbits. This bound is close to optimal since Ω(n) is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits.}}, author = {{Adler, Micah and Räcke, Harald and Sivadasan, Naveen and Sohler, Christian and Vöcking, Berthold}}, booktitle = {{Proceedings of the 29th International Colloquium on Automata, Languages and Programming}}, isbn = {{9783540438649}}, issn = {{0302-9743}}, title = {{{Randomized Pursuit-Evasion in Graphs}}}, doi = {{10.1007/3-540-45465-9_77}}, year = {{2002}}, } @inbook{16723, author = {{Meyer auf der Heide, Friedhelm and Kumar, Mohan and Nikoletseas, Sotiris and Spirakis, Paul}}, booktitle = {{Euro-Par 2002 Parallel Processing}}, isbn = {{9783540440499}}, issn = {{0302-9743}}, title = {{{Mobile Computing, Mobile Networks}}}, doi = {{10.1007/3-540-45706-2_133}}, year = {{2002}}, } @article{18749, author = {{Czumaj, Artur and Sohler, Christian}}, isbn = {{9783540422877}}, issn = {{0302-9743}}, journal = {{Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP)}}, pages = {{493--505}}, title = {{{Testing Hypergraph Coloring}}}, doi = {{10.1007/3-540-48224-5_41}}, year = {{2001}}, } @inproceedings{18964, author = {{Lukovszki, Tamás and Maheshwari, Anil and Zeh, Norbert}}, booktitle = {{Proceedings of the 21st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2001), LNCS}}, isbn = {{9783540430025}}, issn = {{0302-9743}}, title = {{{I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems}}}, doi = {{10.1007/3-540-45294-x_21}}, year = {{2001}}, } @inproceedings{18152, abstract = {{Computing the spectral decomposition of a normal matrix is among the most frequent tasks to numerical mathematics. A vast range of methods are employed to do so, but all of them suffer from instabilities when applied to degenerate matrices, i.e., those having multiple eigenvalues. We investigate the spectral representation's effectivity properties on the sound formal basis of computable analysis. It turns out that in general the eigenvectors cannot be computed from a given matrix. If however the size of the matrix' spectrum (=number of different eigenvalues) is known in advance, it can be diagonalized effectively. Thus, in principle the spectral decomposition can be computed under remarkably weak non-degeneracy conditions.}}, author = {{Ziegler, Martin and Brattka, Vasco}}, booktitle = {{Proceedings of the 4th Workshop on Computability and Complexity in Analysis (CCA'2000)}}, isbn = {{9783540421979}}, issn = {{0302-9743}}, pages = {{378--388}}, title = {{{A Computable Spectral Theorem}}}, doi = {{10.1007/3-540-45335-0_23}}, volume = {{2064}}, year = {{2001}}, } @inbook{16493, author = {{Meyer auf der Heide, Friedhelm}}, booktitle = {{Graph-Theoretic Concepts in Computer Science}}, isbn = {{9783540427070}}, issn = {{0302-9743}}, title = {{{Data Management in Networks}}}, doi = {{10.1007/3-540-45477-2_2}}, volume = {{2204}}, year = {{2001}}, } @inbook{16494, author = {{Meyer auf der Heide, Friedhelm and Wanka, Rolf}}, booktitle = {{Computational Science - ICCS 2001}}, isbn = {{9783540422334}}, issn = {{0302-9743}}, title = {{{Parallel Bridging Models and Their Impact on Algorithm Design}}}, doi = {{10.1007/3-540-45718-6_68}}, year = {{2001}}, } @book{16722, editor = {{Meyer auf der Heide, Friedhelm}}, isbn = {{9783540424932}}, issn = {{0302-9743}}, publisher = {{Springer }}, title = {{{Algorithms — ESA 2001, 9th Annual European Symposium Århus, Denmark}}}, doi = {{10.1007/3-540-44676-1}}, year = {{2001}}, } @inbook{3023, author = {{Blömer, Johannes}}, booktitle = {{Automata, Languages and Programming}}, isbn = {{9783540677154}}, issn = {{0302-9743}}, pages = {{248--259}}, publisher = {{Springer Berlin Heidelberg}}, title = {{{Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices}}}, doi = {{10.1007/3-540-45022-x_22}}, year = {{2000}}, }