Arrow Research search

Author name cluster

Philipp Woelfel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers
2 author rows

Possible papers

18

FOCS Conference 2014 Conference Paper

Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM

  • George Giakkoupis
  • Philipp Woelfel

In this paper we settle an open question by determining the remote memory reference (RMR) complexity of randomized mutual exclusion, on the distributed shared memory model (DSM) with atomic registers, in a weak but natural (and stronger than oblivious) adversary model. In particular, we present a mutual exclusion algorithm that has constant expected amortized RMR complexity and is deterministically deadlock free. Prior to this work, no randomized algorithm with o(log n/log log n) RMR complexity was known for the DSM model. Our algorithm is fairly simple, and compares favorably with one by Bender and Gilbert (FOCS 2011) for the CC model, which has expected amortized RMR complexity O(log 2 log n) and provides only probabilistic deadlock freedom.

Details

STOC Conference 2003 Conference Paper

Almost random graphs with simple hash functions

  • Martin Dietzfelbinger
  • Philipp Woelfel

We describe a simple randomized construction for generating pairs of hash functions h 1 ,h 2 from a universe U to ranges V = [m] = (0,1,...,m-1) and W = [m] so that for every key set S ⊆ U with n = |S| ≤ m/(1 + ε) the (random) bipartite (multi)graph with node set V ∪ W and edge set (h 1 (x),h 2 (x))| x ∈ S exhibits a structure that is essentially random. The construction combines d-wise independent classes for d a relatively small constant with the well-known technique of random offsets. While keeping the space needed to store the description of h 1 and h 2 at O(n ζ ), for ζ < 1 fixed arbitrarily, we obtain a much smaller (constant) evaluation time than previous constructions of this kind, which involved Siegel's high-performance hash classes. The main new technique is the combined analysis of the graph structure and the inner structure of the hash functions, as well as a new way of looking at the cycle structure of random (multi)graphs. The construction may be applied to improve on Pagh and Rodler's "cuckoo hashing" (2001), to obtain a simpler and faster alternative to a recent construction of Ostlin and Pagh (2002/03) for simulating uniform hashing on a key set S, and to the simulation of shared memory on distributed memory machines. We also describe a novel way of implementing (approximate) d-wise independent hashing without using polynomials.

Details

MFCS Conference 2003 Conference Paper

Symbolic Topological Sorting with OBDDS

  • Philipp Woelfel

Abstract We present a symbolic OBDD algorithm for topological sorting which requires O (log 2 N ) OBDD operations. Then we analyze its true runtime for the directed grid graph and show an upper bound of O (log 4 N ). This is the first true runtime analysis of a symbolic OBDD algorithm for a fundamental graph problem, and it demonstrates that one can hope that the algorithm behaves well for sufficiently structured inputs.

Details

MFCS Conference 2002 Conference Paper

A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and Its Applications

  • Beate Bollig
  • Philipp Woelfel

Abstract We present a new lower bound technique for a restricted Branching Program model, namely for nondeterministic graph-driven read-once Branching Programs (g. d. -BP1s). The technique is derived by drawing a connection between ω -nondeterministic g. d. -BP1s and ω-nondeterministic communication complexity (for the nondeterministic acceptance modes \( \omega \in \{ \vee, \wedge, \oplus \} ) \) We apply the technique in order to prove an exponential lower bound for integer multiplication for ω-nondeterministic well-structured g. d. -BP1s. (For ω = ⊕ an exponential lower bound was already obtained in [ 5 ] by using a different technique.) Further, we use the lower bound technique to prove for an explicitly defined fnction which can be represented by polynomial size ω-nondeterministic BP1s that it has exponential complexity in the ω-nondeterministic well-structured g. d. -BP1 model for \( \omega \in \{ \vee, \oplus \} \). This answers an open question from Brosenne, Homeister, and Waack [ 7 ], whether the nondeterministic BP1 model is in fact more powerful than the well-structured graph-driven variant.

Details

MFCS Conference 1999 Conference Paper

Efficient Strongly Universal and Optimally Universal Hashing

  • Philipp Woelfel

Abstract New hash families are analyzed, mainly consisting of the hash functions h a, b: {0, .. ., u − 1} → {0, .. ., r − 1}, x ↦ (( ax + b ) mod( kr )) div k. Universal classes of such functions have already been investigated in [ 5, 6 ], and used in several applications, e. g. [ 3, 9 ]. The new constructions which are introduced here, improve in several ways upon the former results. Some of them achieve a smaller universality parameter, i. e. , two keys collide under a randomly chosen function with a smaller probability. In fact, an optimally universal hash class is presented, which means that the universality parameter achieves the minimum possible value. Furthermore, the bound of the universality parameter of a known, almost strongly universal hash family is improved, and it is shown how to reduce the size of a known class, retaining its properties. Finally, a new composition technique for constructing hash classes for longer keys is presented. Its application leads to efficient hash families which consist of linear functions over the ring of polynomials over ℤ m.

Details