Efficient Gauss elimination for near-quadratic matrices with one short random block per row, with applications. - In: 27th Annual European Symposium on Algorithms, (2019), S. 39:1-39:18
https://doi.org/10.4230/LIPIcs.ESA.2019.39
Dense peelable random uniform hypergraphs. - In: 27th Annual European Symposium on Algorithms, (2019), S. 38:1-38:16
https://doi.org/10.4230/LIPIcs.ESA.2019.38
Determining minimum hash width for hash chains. - In: CECC 2019, (2019), article no. 18, 5 Seiten
https://doi.org/10.1145/3360664.3360682
Sequential and parallel algorithms and data structures : the basic toolbox. - Cham : Springer, 2019. - xv, 509 Seiten ISBN 978-3-030-25208-3
Literaturverzeichnis: Seite 467-485
Constant-time retrieval with O(log m) extra bits. - In: 36th International Symposium on Theoretical Aspects of Computer Science, (2019), 24, S. 24:1-24:16
https://doi.org/10.4230/LIPIcs.STACS.2019.24
Dual-Pivot quicksort: optimality, analysis and zeros of associated lattice paths. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 28 (2019), 4, S. 485-518
https://doi.org/10.1017/S096354831800041X
A subquadratic algorithm for 3XOR. - In: 43rd International Symposium on Mathematical Foundations of Computer Science, (2018), 59, insges. 15 S.
https://doi.org/10.4230/LIPIcs.MFCS.2018.59
Universal hashing via integer arithmetic without primes, revisited. - In: Adventures Between Lower Bounds and Higher Altitudes, (2018), S. 257-279
https://doi.org/10.1007/978-3-319-98355-4_15
Theory and applications of hashing : report from Dagstuhl Seminar 17181. - In: , ISSN 2192-5283, Bd. 7 (2017), 5, S. 1-21
http://dx.doi.org/10.4230/DagRep.7.5.1
How good is Multi-Pivot Quicksort?. - In: ACM transactions on algorithms, ISSN 1549-6333, Bd. 13 (2016), 1, Article No. 8, insges. 47 S.
https://doi.org/10.1145/2963102
Optimal partitioning for dual-pivot quicksort. - In: ACM transactions on algorithms, ISSN 1549-6333, Bd. 12 (2016), 2, Article No. 18, insges. 36 S.
A preliminary version of this work appeared in the Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP), Part 1, 33-44, 2013
https://doi.org/10.1145/2743020
On testing single connectedness in directed graphs and some related problems. - In: Information processing letters, ISSN 1872-6119, Bd. 115 (2015), 9, S. 684-688
http://dx.doi.org/10.1016/j.ipl.2015.04.008
Towards optimal degree distributions for left-perfect matchings in random bipartite graphs. - In: Theory of computing systems, ISSN 1433-0490, Bd. 56 (2015), 4, S. 593-611
http://dx.doi.org/10.1007/s00224-014-9577-1
Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25 - 29, 2014 ; proceedings. - Berlin [u.a.] : Springer, 2014. - (Lecture notes in computer science ; ...)
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithmica, ISSN 1432-0541, Bd. 70 (2014), 3, S. 428-456
It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611-622, Springer, Berlin, 2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash size s the probability of a rehash is O(1/n^(s+1)), the lookup time and the deletion time are O(s) in the worst case, and the amortized expected insertion time is O(s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81-102, 2010) (resp. (log n)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629-638, 2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant.
http://dx.doi.org/10.1007/s00453-013-9840-x
Tight lower bounds for greedy routing in higher-dimensional small-world grids. - In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, (2014), S. 816-829
We consider Kleinberg's celebrated small world graph model (Kleinberg, 2000), in which a D-dimensional grid {0,\dots,n-1}^D is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to |u-v|^(-D). He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O((log n)^2) between any two nodes. We prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.,e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of |u-v|. In particular, we show that for such graphs the expected greedy routing time between two arbitrary nodes s and t is Omega((log|s-t|)^2). This lower bound proves and strengthens a conjecture by Aspnes, Diamadi, and Shah (2000). In order to obtain the result, we introduce a novel proof technique: We define a so-called budget game, in which a token travels over a game board, from one end to the other, while the player manages a "probability budget". In each round, the player "bets" part of her remaining probability budget on step sizes. A step size is chosen at random according to a probability distribution of the player's bet. The token then makes progress as determined by the chosen step size, while some of the player's bet is removed from her probability budget. We prove a tight lower bound for such a budget game, and then obtain a lower bound for greedy routing in the D-dimensional grid by a reduction.
Optimal partitioning for dual pivot quicksort. - In: Automata, languages, and programming, (2013), S. 33-44
https://doi.org/10.1007/978-3-642-39206-1_4
On randomness in Hash functions. - In: 29th International Symposium on Theoretical Aspects of Computer Science, (2012), S. 25-28
In the talk, we shall discuss quality measures for hash functions used in data structures and algorithms, and survey positive and negative results. (This talk is not about cryptographic hash functions.) For the analysis of algorithms involving hash functions, it is often convenient to assume the hash functions used behave fully randomly; in some cases there is no analysis known that avoids this assumption. In practice, one needs to get by with weaker hash functions that can be generated by randomized algorithms. A well-studied range of applications concern realizations of dynamic dictionaries (linear probing, chained hashing, dynamic perfect hashing, cuckoo hashing and its generalizations) or Bloom filters and their variants. A particularly successful and useful means of classification are Carter and Wegman's universal or k-wise independent classes, introduced in 1977. A natural and widely used approach to analyzing an algorithm involving hash functions is to show that it works if a sufficiently strong universal class of hash functions is used, and to substitute one of the known constructions of such classes. This invites research into the question of just how much independence in the hash functions is necessary for an algorithm to work. Some recent analyses that gave impossibility results constructed rather artificial classes that would not work; other results pointed out natural, widely used hash classes that would not work in a particular application. Only recently it was shown that under certain assumptions on some entropy present in the set of keys even 2-wise independent hash classes will lead to strong randomness properties in the hash values. The negative results show that these results may not be taken as justification for using weak hash classes indiscriminately, in particular for key sets with structure. When stronger independence properties are needed for a theoretical analysis, one may resort to classic constructions. Only in 2003 it was found out how full randomness can be simulated using only linear space overhead (which is optimal). The "split-and-share" approach can be used to justify the full randomness assumption in some situations in which full randomness is needed for the analysis to go through, like in many applications involving multiple hash functions (e.g., generalized versions of cuckoo hashing with multiple hash functions or larger bucket sizes, load balancing, Bloom filters and variants, or minimal perfect hash function constructions). For practice, efficiency considerations beyond constant factors are important. It is not hard to construct very efficient 2-wise independent classes. Using k-wise independent classes for constant k bigger than 3 has become feasible in practice only by new constructions involving tabulation. This goes together well with the quite new result that linear probing works with 5-independent hash functions. Recent developments suggest that the classification of hash function constructions by their degree of independence alone may not be adequate in some cases. Thus, one may want to analyze the behavior of specific hash classes in specific applications, circumventing the concept of k-wise independence. Several such results were recently achieved concerning hash functions that utilize tabulation. In particular if the analysis of the application involves using randomness properties in graphs and hypergraphs (generalized cuckoo hashing, also in the version with a "stash", or load balancing), a hash class combining k-wise independence with tabulation has turned out to be very powerful.
http://dx.doi.org/10.4230/LIPIcs.STACS.2012.25
Explicit and efficient hash families suffice for cuckoo hashing with a stash. - In: Algorithms - ESA 2012, (2012), S. 108-120
https://doi.org/10.1007/978-3-642-33090-2_11
Towards optimal degree-distributions for left-perfect matchings in random bipartite graphs. - In: Computer Science – Theory and Applications, (2012), S. 99-111
http://dx.doi.org/10.1007/978-3-642-30642-6_11
A more reliable greedy heuristic for maximum matchings in sparse random graphs. - In: Experimental Algorithms, (2012), S. 148-159
http://dx.doi.org/10.1007/978-3-642-30850-5_14
Cuckoo hashing with pages. - In: Algorithms - ESA 2011, (2011), S. 615-627
http://dx.doi.org/10.1007/978-3-642-23719-5
Precision, local search and unimodal functions. - In: Algorithmica, ISSN 1432-0541, Bd. 59 (2011), 3, S. 301-322
We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary (base-2) and reflected Gray code representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using the reflected Gray code does so in O ((log n)2) steps. A(1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O ((log n)2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega ((log n)2) holds regardless of the choice of mutation distribution. For continuous multimodal functions, the algorithm also locates the global optimum in O((log n)2). Finally, we show that it is not possible for a black box algorithm to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).
http://dx.doi.org/10.1007/s00453-009-9352-x
Algorithms unplugged. - Berlin, Heidelberg : Springer-Verlag, 2011. - Online-Ressource (X, 406 S.) ISBN 978-3-642-15328-0
Description based upon print version of record
Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas - they facilitate new applications in science, medicine, production, logistics, traffic, communi cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs - for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity - the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.
http://dx.doi.org/10.1007/978-3-642-15328-0
Ingo Wegener: seine Bücher. - In: Informatik-Spektrum, ISSN 1432-122X, Bd. 33 (2010), 4, S. 485
http://dx.doi.org/10.1007/s00287-010-0463-1
Tight thresholds for cuckoo hashing via XORSAT. - In: Automata, languages and programming, (2010), S. 213-225
http://dx.doi.org/10.1007/978-3-642-14165-2_19
Tight bounds for blind search on the integers and the reals. - In: Combinatorics, probability & computing, ISSN 1469-2163, Bd. 19 (2010), 5/6, S. 711-728
https://doi.org/10.1017/S0963548309990599
Experimental variations of a theoretically good retrieval data structure. - In: Algorithms - ESA 2009, (2009), S. 742-751
A retrieval data structure implements a mapping from a set S of n keys to range R={0,1}^r , e.g. given by a list of key-value pairs (x,v)?S×R, but an element outside S may be mapped to any value. Asymptotically, minimal perfect hashing allows to build such a data structure that needs n*log_2(e)+nr+o(n) bits of memory and has constant evaluation time. Recently, data structures based on other approaches have been proposed that have linear construction time, constant evaluation time and space consumption O(nr) bits or even (1+?)nr bits for arbitrary ?>0. This paper explores the practicability of one such theoretically very good proposal, bridging a gap between theory and real data structures.
http://dx.doi.org/10.1007/978-3-642-04128-0_66
Hash, displace, and compress. - In: Algorithms - ESA 2009, (2009), S. 682-693
A hash function h, i.e., a function from the set U of all keys to the range range [m]={0,...,m-1} is called a perfect hash function (PHF) for a subset S?U of size n?m if h is 1-1 on S. The important performance parameters of a PHF are representation size, evaluation time and construction time. In this paper, we present an algorithm that permits to obtain PHFs with expected representation size very close to optimal while retaining O(n) expected construction time and O(1) evaluation time in the worst case. For example in the case m=1.23n we obtain a PHF that uses space 1.4 bits per key, and for m=1.01n we obtain space 1.98 bits per key, which was not achievable with previously known methods. Our algorithm is inspired by several known algorithms; the main new feature is that we combine a modification of Pagh's hash-and-displaceъ approach with data compression on a sequence of hash function indices. Our algorithm can also be used for k-perfect hashing, where at most k keys may be mapped to the same value.
http://dx.doi.org/10.1007/978-3-642-04128-0_61
Perfect hashing for state spaces in BDD representation. - In: KI 2009: advances in artificial intelligence, (2009), S. 33-40
http://dx.doi.org/10.1007/978-3-642-04617-9_5
Brief announcement: tight lower bounds for greedy routing in uniform small world rings. - In: Proceedings of the 2009 ACM Symposium on Principles of Distributed Computing, (2009), S. 300-301
Motivated by Kleinberg's Small World Graph model and packet routing strategies in peer-to-peer networks, greedy routing algorithms on augmented networks have been investigated thoroughly. We prove tight lower bounds for one- and two-sided greedy routing on augmented rings.
Tight lower bounds for greedy routing in uniform small world rings. - In: Proceedings of the 2009 ACM International Symposium on Theory of Computing, (2009), S. 591-600
We consider augmented ring-based networks with vertices 0,...,n-1, where each vertex is connected to its left and right neighbor and possibly to some further vertices (called long range contacts). The outgoing edges of a vertex v are obtained by choosing a subset D of {1,2,...n-1}, with 1, n-1 in D, at random according to a probability distribution mu on all such D and then for each i in D connecting v to (v+i) mod n by a unidirectional link. The choices for different v are done independently and uniformly in the sense that the same distribution mu is used for all v. The expected number of long range contacts is l=E(|D|)-2. Motivated by Kleinberg's (2000) Small World Graph model and packet routing strategies for peer-to-peer networks, the greedy routing algorithm on augmented rings, where a packet sitting in a node v is routed to the neighbor of v closest to the destination of the package, has been investigated thoroughly, both for the "one-sided case", where packets can travel only in one direction, and the "two-sided case", where there is no such restriction. In this paper, for both the one-sided and the two-sided case and for an arbitrary distribution mu, we prove a lower bound of Omega((log n)2/l) on the expected number of hops that are needed by the greedy strategy to route a package between two randomly chosen vertices on the ring. This bound is tight for Omega(1)<=l=O(log n).
Applications of a splitting trick. - In: Automata, languages and programming, (2009), S. 354-365
We study applications of a simple method for circumventing the "full randomness assumption" when building a hashing-based data structure for a set S of keys. The general approach is to "split" S into "pieces" S_i , by a splitting hash function. On a piece S_i, a method or data structure for generating full randomness is used that uses more space than |S_i|. Under certain circumstances, this data structure can be "shared" among the constructions for the pieces S_i , which leads to a tighter overall space bound. The method was introduced in the context of cuckoo hashing and its variants, but it seems to have wider applicability. To demonstrate its power and some subtleties, we study three new applications, improving previous constructions: (i) Space-efficient simulation of full randomness on S (following work by Pagh and Pagh (2003/08) and Dietzfelbinger and Woelfel (2003)); (ii) Construction of highly independent functions in the style of Siegel (1989/2004); (iii) One-probe schemes as in work by Buhrman, Miltersen, Radhakrishnan, and Venkatesh (2000/02) and Pagh and Pagh (2002).
http://dx.doi.org/10.1007/978-3-642-02927-1_30
On risks of using cuckoo hashing with simple universal hash classes. - In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, (2009), S. 795-804
Weaknesses of Cuckoo hashing with a simple universal hash class: the case of large universes. - In: SOFSEM 2009: theory and practice of computer science, (2009), S. 217-228
http://dx.doi.org/10.1007/978-3-540-95891-8_22
Precision, local search and unimodal functions. - In: GECCO 2008, (2008), S. 771-778
We investigate the effects of precision on the efficiency of various local search algorithms on 1-D unimodal functions. We present a (1+1)-EA with adaptive step size which finds the optimum in O(log n) steps, where n is the number of points used. We then consider binary and Gray representations with single bit mutations. The standard binary method does not guarantee locating the optimum, whereas using Gray code does so in O((log n)^2) steps. A (1+1)-EA with a fixed mutation probability distribution is then presented which also runs in O((log n)^2). Moreover, a recent result shows that this is optimal (up to some constant scaling factor), in that there exist unimodal functions for which a lower bound of Omega((log n)^2) holds regardless of the choice of mutation distribution. Finally, we show that it is not possible for a black box algorithms to efficiently optimise unimodal functions for two or more dimensions (in terms of the precision used).
Tight bounds for blind search on the integers. - Ilmenau : Univ.-Bibliothek. - Online-Ressource (PDF-Datei: 12 S., 669,8 KB)Onlineausg.: Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science : STACS 2008, 21 - 23 February, Bordeaux, France / Susanne Albers; Pascal Weil (eds.). - Wadern : IBFI Schloss Dagstuhl, 2008. - ISBN 978-3-939897-06-4, S. 241-252
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a "blind'' optimization strategy.
http://nbn-resolving.de/urn:nbn:de:0030-drops-13486
Succinct data structures for retrieval and approximate membership (extended abstract). - In: , (2008), S. 385-396
The retrieval problem is the problem of associating data with keys in a set. Formally, the data structure must store a function f : U -> {0,1}^r that has specified values on the elements of a given subset S of U, |S|=n, but may have any value on elements outside S. All known methods (e.g. those based on perfect hash functions), induce a space overhead of (n) bits over the optimum, regardless of the evaluation time. - We show that for any k query time O(k) can be achieved using space that is within a factor 1+exp(-k) of optimal, asymptotically for large n. The time to construct the data structure is O(n), expected. If we allow logarithmic evaluation time, the additive overhead can be reduced to O(log log n) bits whp. - Further, we note a general reduction that transfers the results on retrieval into analogous results on approximate membership, a problem traditionally addressed using Bloom filters. This makes it possible to get arbitrarily close to the lower bound. The evaluation procedures of our data structures are extremely simple. For the results stated above we assume free access to fully random hash functions. This assumption can be justified using extra space o(n) to simulate full randomness on a RAM.
http://dx.doi.org/10.1007/978-3-540-70575-8_32
[Rezension von: Dasgupta, Sanjoy; Papadimitriou, Christos H.; Vazirani, Umesh Virkumar, Algorithms...]. - In: , ISSN 1876-7745, Bd. 2 (2008), 2, S. 131-136
http://dx.doi.org/10.1016/j.cosrev.2008.03.001
A dictionary implementation based on dynamic perfect hashing. - In: Journal of experimental algorithmics, ISSN 1084-6654, Bd. 12.2008, 1.11, insges. 25 S.
We describe experimental results on an implementation of a dynamic dictionary. The basis of our implementation is dynamic perfect hashingъ as described by Dietzfelbinger et al. (SIAM J. Computing 23, 1994, pp. 738--761), an extension of the storage scheme proposed by Fredman et al. (J. ACM 31, 1984, pp. 538--544). At the top level, a hash function is used to partition the keys to be stored into several sets. On the second level, there is a perfect hash function for each of these sets. This technique guarantees O(1) worst-case time for lookup and expected O(1) amortized time for insertion and deletion, while only linear space is required. We study the practical performance of dynamic perfect hashing and describe improvements of the basic scheme. The focus is on the choice of the hash function (both for integer and string keys), on the efficiency of rehashing, on the handling of small buckets, and on the space requirements of the implementation.
http://doi.acm.org/10.1145/1370596.1370602
Taschenbuch der Algorithmen. - Berlin, Heidelberg : Springer-Verlag, 2008. - Online-Ressource (X, 448 S.). - (eXamen.press) ISBN 978-3-540-76394-9
Heriber
http://dx.doi.org/10.1007/978-3-540-76394-9
Tight bounds for blind search on the integers. - Dortmund : TU, Secretary of the SFB 531, 2008. - 13 Bl.. - (Reihe Computational Intelligence ; 240)
Probabilistic methods in the design and analysis of algorithms : 07391 abstracts collection ; Dagstuhl seminar. - [Wadern] : [Internat. Begegnungs- und Forschungszentrum für Informatik], 2007. - Online-Ressource (PDF-Datei: 18 S., 240 KB). - (Dagstuhl seminar proceedings ; 07391)
http://d-nb.info/991699130/34
Design strategies for minimal perfect hash functions. - In: Stochastic algorithms: foundations and applications, (2007), S. 2-17
http://dx.doi.org/10.1007/978-3-540-74871-7
A characterization of average case communication complexity. - In: Information processing letters, ISSN 1872-6119, Bd. 101 (2007), 6, S. 245-249
It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.
http://dx.doi.org/10.1016/j.ipl.2006.10.006
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Theoretical computer science, Bd. 380 (2007), 1/2, S. 47-68
We study a particular aspect of the balanced allocation paradigm (also known as the "two-choices paradigm"): constant sized bins, packed as tightly as possible. Let d >= 1 be fixed, and assume there are m bins of capacity d each. To each of n <= d*m$ balls two possible bins are assigned at random. How close can dm/n = 1 + epsilon be to 1 so that with high probability each ball can be put into one of the two bins assigned to it, without any bin overflowing? We show that epsilon > (2/e)^(d-1) is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for epsilon > beta^d, for some constant beta < 1. An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing (Pagh and Rodler, 2004), we consider a hash table with m positions, each representing a bucket of capacity d >= 1. Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key x may go to bin h_1(x) or to bin h_2(x)? We obtain an implementation of a dictionary that accommodates n keys in m = (1+epsilon)n/d buckets of size d = O(log(1/epsilon)), so that key x resides in bucket h_1(x) or h_2(x). For a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. If d >= 1 + 3.26 * ln(1/epsilon), a static arrangement exists with high probability. If d >= 16 * \ln(1/epsilon), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/epsilon)^(O(log log(1/epsilon))).
http://dx.doi.org/10.1016/j.tcs.2007.02.054
On the probability of rendezvous in graphs. - In: Random structures & algorithms, ISSN 1098-2418, Bd. 26 (2005), 3, S. 266-288
In a simple graph G without isolated nodes the following random experiment is carried out: each node chooses one of its neighbors uniformly at random. We say a rendezvous occurs if there are adjacent nodes u and v such that u chooses v and v chooses u; the probability that this happens is denoted by s(G). Métivier, Saheb, and Zemmari [Randomized rendezvous, Algorithms, trees, combinatorics, and probabilities, Eds. G. Gardy and A. Mokkadem, Trends in Mathematics, 183-194. Birkhäuser, Boston, 2000.] asked whether it is true that s(G) s(Kn) for all n-node graphs G, where Kn is the complete graph on n nodes. We show that this is the case. Moreover, we show that evaluating s(G) for a given graph G is a #P-complete problem, even if only d-regular graphs are considered, for any d 5.
https://doi.org/10.1002/rsa.20032
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Automata, languages and programming, (2005), S. 166-178
http://dx.doi.org/10.1007/11523468_14
Primality testing in polynomial time : from randomized algorithms to "PRIMES is in P". - Berlin : Springer, 2004. - Online-Ressource (X, 147p. Also available online). - (Lecture notes in computer science ; 3000) ISBN 978-3-540-25933-6
This book is devoted to algorithms for the venerable primality problem: Given a natural number n, decide whether it is prime or composite. The problem is basic in number theory, efficient algorithms that solve it, i.e., algorithms that run in a number of computational steps which is polynomial in the number of digits needed to write n, are important for theoretical computer science and for applications in algorithmics and cryptology. This book gives a self-contained account of theoretically and practically important efficient algorithms for the primality problem, covering the randomized algorithms by Solovay-Strassen and Miller-Rabin from the late 1970s as well as the recent deterministic algorithm of Agrawal, Kayal, and Saxena. The textbook is written for students of computer science, in particular for those with a special interest in cryptology, and students of mathematics, and it may be used as a supplement for courses or for self-study
https://doi.org/10.1007/b12334
Gossiping and broadcasting versus computing functions in networks. - In: Discrete applied mathematics, ISSN 1872-6771, Bd. 137 (2004), 2, S. 127-153
https://doi.org/10.1016/S0166-218X(03)00257-9
The analysis of a recombinative hill-climber on H-IFF. - In: IEEE transactions on evolutionary computation, ISSN 1089-778X, Bd. 7 (2003), 5, S. 417-423
Almost random graphs with simple hash functions. - In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, (2003), S. 629-638
A case against using Stirling's formula. - In: Bulletin of the European Association for Theoretical Computer Science, EATCS, ISSN 0252-9742, Bd. 80 (2003), S. 153-158
On the probability of rendezvous in graphs. - Saarbrücken : Max-Planck-Inst. für Informatik, Bibliothek & Dokumentation, 2003. - 27 S. - (Forschungsberichte des Max-Planck-Instituts für Informatik ; 2003-1-006)
Almost random graphs with simple hash functions. - Saarbrücken : Max-Planck-Inst. für Informatik, Bibliothek & Dokumentation, 2003. - 20 S. - (Forschungsberichte des Max-Planck-Instituts für Informatik ; 2003-1-005)
The probability of a rendezvous is minimal in complete graphs. - In: Algorithms and Computation, (2002), S. 55-66
http://dx.doi.org/10.1007/3-540-36136-7_6
The analysis of a recombinative hill climber on HIFF. - Dortmund : Secretary of the SFB 531, 2002. - 6 Bl. - (Reihe computational intelligence ; 138)
Simple minimal perfect hashing in less space. - In: Algorithms — ESA 2001, (2001), S. 109-120
http://dx.doi.org/10.1007/3-540-44676-1_9
On different models for packet flow in multistage interconnection networks. - In: Fundamenta informaticae, ISSN 0169-2968, Bd. 46 (2001), 4, S. 287-314
Linear hash functions. - In: Journal of the ACM, ISSN 1557-735X, Bd. 46 (1999), 5, S. 667-683
https://doi.org/10.1145/324133.324179