PWPhilipp Woelfel
Philipp Woelfel
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Philipp Woelfel has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Martin Dietzfelbinger
Technische Universität Ilmenau
5 shared publications - Jonathan E. Rowe
University of Birmingham
3 shared publications Ingo Wegener
Fakultät für Informatik, Technische Universität Dortmund, 44221 Dortmund, Germany
2 shared publications- Ingo Wegener
FB Informatik Universität Dortmund LS2 44221 Dortmund Germany
2 shared publications - Martin Aumüller
IT University of Copenhagen, Copenhagen, Denmark
2 shared publications
Latest Publications
- 8 October 2013
- Published by Springer Nature in Algorithmica
- Vol. 70 (3) , 428-456
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
- 8 October 2013
- Published by Springer Nature in Algorithmica
- Vol. 70 (3) , 428-456
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
- Open Access
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
It is shown that for cuckoo hashing with a stash as proposed by Kirsch, Mitzenmacher, and Wieder (2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with stash size $s$ the probability of a rehash is $O(1/n^{s+1})$, and the evaluation time is $O(s)$. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (2010) (resp. $\Theta(\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 (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. As a byproduct, an algorithm for simulating uniform hashing is obtained. While it requires about twice as much space as the most space efficient solutions, it is attractive because of its simple and direct structure.Open AccessExplicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
It is shown that for cuckoo hashing with a stash as proposed by Kirsch, Mitzenmacher, and Wieder (2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with stash size $s$ the probability of a rehash is $O(1/n^{s+1})$, and the evaluation time is $O(s)$. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (2010) (resp. $\Theta(\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 (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. As a byproduct, an algorithm for simulating uniform hashing is obtained. While it requires about twice as much space as the most space efficient solutions, it is attractive because of its simple and direct structure. - 18 December 2009
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 19 (5-6) , 711-728
Tight Bounds for Blind Search on the Integers and the Reals
We analyse a simple random process in which a token is moved in the interval A = {0, . . ., n}. Fix a probability distribution μ over D = {1, . . ., n}. Initially, the token is placed in a random position in A. In round t, a random step sized is chosen according to μ. If the token is in position x ≥ d, then it is moved to position x − d. Otherwise it stays put. Let TX be the number of rounds until the token reaches position 0. We show tight bounds for the expectation Eμ(TX) of TX for varying distributions μ. More precisely, we show that $\min_\mu\{\E_\mu(T_X)\}=\Theta\bigl((\log n)^2\bigr)$ . The same bounds are proved for the analogous continuous process, where step sizes and token positions are real values in [0, n + 1), and one measures the time until the token has reached a point in [0, 1). For the proofs, 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.- 18 December 2009
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 19 (5-6) , 711-728
Tight Bounds for Blind Search on the Integers and the Reals
We analyse a simple random process in which a token is moved in the interval A = {0, . . ., n}. Fix a probability distribution μ over D = {1, . . ., n}. Initially, the token is placed in a random position in A. In round t, a random step sized is chosen according to μ. If the token is in position x ≥ d, then it is moved to position x − d. Otherwise it stays put. Let TX be the number of rounds until the token reaches position 0. We show tight bounds for the expectation Eμ(TX) of TX for varying distributions μ. More precisely, we show that $\min_\mu\{\E_\mu(T_X)\}=\Theta\bigl((\log n)^2\bigr)$ . The same bounds are proved for the analogous continuous process, where step sizes and token positions are real values in [0, n + 1), and one measures the time until the token has reached a point in [0, 1). For the proofs, 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.- Open Access
- 13 August 2009
- Published by Springer Nature in Algorithmica
- Vol. 59 (3) , 301-322
Precision, Local Search and Unimodal Functions
- 13 August 2009
- Published by Springer Nature in Algorithmica
- Vol. 59 (3) , 301-322
Open AccessPrecision, Local Search and Unimodal Functions
- Open Access
Tight Bounds for Blind Search on the Integers
We analyze a simple random process in which a token is moved in the interval $A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,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 $a\geq 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)\=\Theta((\log n)^2)$. 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.Open AccessTight Bounds for Blind Search on the Integers
We analyze a simple random process in which a token is moved in the interval $A=\{0,...,n\$: Fix a probability distribution $\mu$ over $\{1,...,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 $a\geq 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)\=\Theta((\log n)^2)$. 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. - 5 October 2007
- Published by Springer Nature in computational complexity
- Vol. 16 (3) , 298-323
New Results on the Complexity of the Middle Bit of Multiplication
- 5 October 2007
- Published by Springer Nature in computational complexity
- Vol. 16 (3) , 298-323
New Results on the Complexity of the Middle Bit of Multiplication