Publications

2014
[57] Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids (Martin Dietzfelbinger, Philipp Woelfel), 24th SODA, 2014. Accepted [info]
2013
[56] Gossip Protocols for Renaming and Sorting (George Giakkoupis, Anne-Marie Kermarrec, Philipp Woelfel), 27th DISC, Springer, 2013. Accepted [info]
[55] An O(sqrt n) Space Bound for Obstruction-Free Leader Election (George Giakkoupis, Maryam Helmi, Lisa Higham, Philipp Woelfel), 27th DISC, Springer, 2013. Accepted [info]
[54] An Optimal Implementation of Fetch-and-Increment (Faith Ellen, Philipp Woelfel), 27th DISC, Springer, 2013. Accepted [info]
[53] Brief Announcement: Resettable Objects and Efficient Memory Reclamation for Concurrent Algorithms (Zahra Aghazadeh, Wojciech Golab, Philipp Woelfel), 32nd PODC, pp. 322--324, 2013. [info] [doi]
[52] Randomized Loose Renaming in O(log log n) Time (Dan Alistarh, James Aspnes, George Giakkoupis, Philipp Woelfel), 32nd PODC, pp. 200--209, 2013. [info] [doi]
[51] Decoupled Speed Scaling: Analysis and Evaluation (Maryam Elahi, Carey Williamson, Philipp Woelfel), Performance Evaluation, Elsevier, 2013. (Invited contribution.) [info] [pdf] [doi]
2012
[50] RMR-Efficient Randomized Abortable Mutual Exclusion (Abhijeet Pareek, Philipp Woelfel), 26th DISC, pp. 267-281, 2012. [info] [doi]
[49] Independence of Tabulation-Based Hash Classes (Toryn Qwyllyn Klassen, Philipp Woelfel), 10th LATIN, pp. 506-517, 2012. [info] [doi]
[48] Strongly Linearizable Implementations: Possibilities and Impossibilities (Maryam Helmi, Lisa Higham, Philipp Woelfel), 31st PODC, pp. 385-394, 2012. [info] [doi]
[47] On the Time and Space Complexity of Randomized Test-And-Set (George Giakkoupis, Philipp Woelfel), 31st PODC, pp. 19-28, 2012. Best paper award. Addendum [info] [doi]
[46] Tight RMR Lower Bounds for Randomized Mutual Exclusion (George Giakkoupis, Philipp Woelfel), 44th STOC, pp. 983-1002, 2012. [info] [doi]
[45] Low Randomness Rumor Spreading via Hashing (George Giakkoupis, Thomas Sauerwald, He Sun, Philipp Woelfel), 29th STACS, pp. 314-325, 2012. [info] [doi]
[44] Decoupled Speed Scaling: Analysis and Evaluation (Maryam Elahi, Carey Williamson, Philipp Woelfel), 9th QEST, pp. 2--12, IEEE Computer Society, 2012. Best paper award [info] [doi]
[43] Efficient Fetch-and-Increment (Faith Ellen, Vijaya Ramachandran, Philipp Woelfel), 26th DISC, pp. 16-30, 2012. [info] [doi]
[42] RMR-efficient implementations of comparison primitives using read and write operations (Wojciech Golab, Danny Hendler, Vassos Hadzilacos, Philipp Woelfel), Distributed Computing 25(2), pp. 109-162, 2012. [info] [doi]
2011
[41] The Space Complexity of Long-Lived and One-Shot Timestamp Implementations (Maryam Helmi, Lisa Higham, Eduardo Pacheco, Philipp Woelfel), 30th PODC, pp. 139-148, 2011. Best paper award [info] [pdf] [doi]
[40] On the Randomness Requirements of Rumor Spreading (George Giakkoupis, Philipp Woelfel), 22nd SODA, pp. 449-461, 2011. [info] [pdf]
[39] Linearizable Implementations Do Not Suffice for Randomized Distributed Computation (Wojciech Golab, Lisa Higham, Philipp Woelfel), 43rd STOC, pp. 373-382, 2011. [info] [pdf] [doi]
[38] Randomized Mutual Exclusion with Sub-Logarithmic RMR-Complexity (Danny Hendler, Philipp Woelfel), Distributed Computing 24(1), pp. 3-19, 2011. (Invited contribution.) [info] [doi]
[37] Precision, Local Search and Unimodal Functions (Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel), Algorithmica 59(3), pp. 301-322, 2011. (Invited contribution.) [info] [doi]
[36] Fully-adaptive algorithms for long-lived renaming (Alex Brodsky, Faith Ellen, Philipp Woelfel), Distributed Computing 24(2), pp. 119-134, 2011. [info] [doi]
2010
[35] Adaptive Randomized Mutual Exclusion in Sub-Logarithmic Expected Time (Danny Hendler, Philipp Woelfel), 29th PODC, pp. 141-150, 2010. [info] [pdf] [doi]
[34] An O(1) RMRs Leader Election Algorithm (Wojciech Golab, Danny Hendler, Philipp Woelfel), SIAM Journal on Computing 39(7), pp. 2726-2760, 2010. [info] [doi]
[33] Tight Bounds for Blind Search on the Integers and the Reals (Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel), Combinatorics, Probability and Computing 19(5-6), pp. 711-728, 2010. [info] [doi]
[32] Separating Deterministic from Randomized Multiparty Communication Complexity (Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel), Theory of Computing 6(1), pp. 201-225, Theory of Computing, 2010. [info] [doi]
2009
[31] Randomized Mutual Exclusion in O(log N/loglog N) RMRs (Danny Hendler, Philipp Woelfel), 28th PODC, pp. 26-35, 2009. [info] [pdf] [doi]
[30] Tight Lower Bounds for Greedy Routing in Uniform Small World Rings (Martin Dietzfelbinger, Philipp Woelfel), 41st STOC, pp. 591-600, 2009. [info] [pdf] [doi]
[29] Representation of graphs by OBDDs (Robin Nunkesser, Philipp Woelfel), Discrete Applied Mathematics 157(2), pp. 247-261, 2009. [info] [doi]
2008
[28] Precision, Local Search and Unimodal Functions (Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel), GECCO, pp. 771-778, 2008. Best paper award, formal theory track [info] [pdf] [doi]
[27] Tight Bounds for Blind Search on the Integers (Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel), 25th STACS, pp. 241-252, 2008. [info] [doi]
[26] Tight RMR Lower Bounds for Mutual Exclusion and Other Problems (Hagit Attiya, Danny Hendler, Philipp Woelfel), 40th STOC, pp. 217-226, 2008. [info] [pdf] [doi]
2007
[25] Constant-RMR Implementations of CAS and Other Synchronization Primitives Using Read and Write Operations (Wojciech Golab, Vassos Hadzilacos, Danny Hendler, Philipp Woelfel), 26th PODC, pp. 3-12, 2007. [info] [pdf] [doi]
[24] Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity (Paul Beame, Matei David, Toni Pitassi, Philipp Woelfel), 34th ICALP, pp. 134-145, 2007. [info] [doi]
[23] New Results on the Complexity of the Middle Bit of Multiplication (Ingo Wegener, Philipp Woelfel), Computational Complexity 16(3), pp. 298-323, 2007. [info] [doi]
2006
[22] Maintaining External Memory Efficient Hash Tables (Philipp Woelfel), 10th RANDOM, pp. 508-519, 2006. [info] [doi]
[21] Asymmetric Balanced Allocation with Simple Hash Functions (Philipp Woelfel), 17th SODA, pp. 424-434, 2006. [info] [pdf] [doi]
[20] An O(1) RMRs Leader Election Algorithm (Wojciech Golab, Danny Hendler, Philipp Woelfel), 25th PODC, pp. 238-274, 2006. [info] [pdf] [doi]
[19] Fully Adaptive Algorithms for Long-Lived Renaming (Alex Brodsky, Faith Ellen, Philipp Woelfel), 20th DISC, pp. 413-427, 2006. [info] [doi]
[18] A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs (Philipp Woelfel), Theoretical Computer Science (special issue on COCOON 2004) 363(1), pp. 76-84, 2006. (Invited contribution.) [info] [doi]
[17] Symbolic Topological Sorting with OBDDs (Philipp Woelfel), Journal of Discrete Algorithms 4(1), pp. 51-71, 2006. [info] [doi]
[16] Parity Graph-Driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication (Beate Bollig, Stephan Waack, Philipp Woelfel), Theoretical Computer Science 362(1-3), pp. 86-99, 2006. [info] [doi]
2005
[15] New Results on the Complexity of the Middle Bit of Multiplication (Ingo Wegener, Philipp Woelfel), 20th CCC, pp. 100-110, 2005. [info] [doi]
[14] Representation of Graphs by OBDDs (Robin Nunkesser, Philipp Woelfel), 16th ISAAC, pp. 1132-1142, 2005. [info] [doi]
[13] Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing (Philipp Woelfel), Journal of Computer and System Sciences 71(4), pp. 520-534, 2005. [info] [doi]
[12] A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications (Beate Bollig, Philipp Woelfel), Theory of Computing Systems 38(6), pp. 671-685, 2005. [info] [doi]
2004
[11] A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs (Philipp Woelfel), 10th COCOON, pp. 23-32, 2004. [info] [doi]
2003
[10] Symbolic Topological Sorting with OBDDs (Philipp Woelfel), 28th MFCS, pp. 671-680, 2003. [info] [doi]
[9] Time-Space Tradeoff Lower Bounds for Integer Multiplication and Graphs of Arithmetic Functions (Martin Sauerhoff, Philipp Woelfel), 35th STOC, pp. 186-195, 2003. [info] [pdf] [doi]
[8] Almost Random Graphs with Simple Hash Functions (Martin Dietzfelbinger, Philipp Woelfel), 35th STOC, pp. 629-638, 2003. [info] [pdf] [doi]
2002
[7] On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism (Philipp Woelfel), 17th CCC, pp. 80-89, 2002. [info] [doi]
[6] A Lower Bound Technique for Restricted Branching Programs and Applications (Philipp Woelfel), 19th STACS, pp. 431-442, 2002. [info] [doi]
[5] Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication (Beate Bollig, Stephan Waack, Philipp Woelfel), 2nd IFIPTCS, pp. 83-94, 2002. [info]
[4] A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications (Beate Bollig, Philipp Woelfel), 27th MFCS, pp. 131-142, 2002. [info] [doi]
2001
[3] New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing (Philipp Woelfel), 18th STACS, pp. 563-574, 2001. (journal version) [info] [doi]
[2] A Read-Once Branching Program Lower Bound of Ω(2^(n/4)) for Integer Multiplication Using Universal Hashing (Beate Bollig, Philipp Woelfel), 33rd STOC, pp. 419-424, 2001. [info] [pdf] [doi]
1999
[1] Efficient Strongly Universal and Optimally Universal Hashing (Philipp Woelfel), 24th MFCS, pp. 262-272, 1999. [draft] [info] [doi]