Publications

K. Aeini, D. Bencivenga, G. Giakkoupis and P. Woelfel. “Simple and Efficient Randomized Wait-Free Locks.” 45th ACM Symposium on Principles of Distributed Computing (PODC), 48–57. ACM (2026). Best paper award.

D. Bencivenga, H. Habashi and P. Woelfel. “Efficient Randomized LL/SC that Preserves History Independence.” Distributed Computing - 40th International Symposium (DISC) (2026). To appear.

B. Bashari, A. Jamadi and P. Woelfel. “Efficient bounded timestamping from standard synchronization primitives.” Distributed Computing 38(3): 297–335. Springer (2025).

B. Bashari, D. Y. C. Chan and P. Woelfel. “A Fully Concurrent Adaptive Snapshot Object for RMWable Shared-Memory.” Distributed Computing - 38th International Symposium (DISC), 7:1–7:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024).

D. Bencivenga, G. Giakkoupis and P. Woelfel. “Faster Randomized Repeated Choice and DCAS.” 43rd ACM Symposium on Principles of Distributed Computing (PODC), 454–464. ACM (2024).

F. Naderi and P. Woelfel. “Strongly Linearizable LL/SC from CAS.” 43rd ACM Symposium on Principles of Distributed Computing (PODC), 443–453. ACM (2024).

D. Y. C. Chan, G. Giakkoupis and P. Woelfel. “Word-Size RMR Tradeoffs for Recoverable Mutual Exclusion.” 42nd ACM Symposium on Principles of Distributed Computing (PODC), 79–89. ACM (2023). Best paper award.

B. Bashari, A. Jamadi and P. Woelfel. “Efficient Bounded Timestamping from Standard Synchronization Primitives.” 42nd ACM Symposium on Principles of Distributed Computing (PODC), 113–123. ACM (2023).

“PODC ’22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25 - 29, 2022.” ACM (2022).

S. M. Hwang and P. Woelfel. “Strongly Linearizable Linked List and Queue.” Principles of Distributed Systems - 25th International Conference, OPODIS 2021, 28:1–28:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021).

B. Bashari and P. Woelfel. “An Efficient Adaptive Partial Snapshot Implementation.” 40th ACM Symposium on Principles of Distributed Computing (PODC), 545–555. ACM (2021).

D. Y. C. Chan and P. Woelfel. “Tight Lower Bound for the RMR Complexity of Recoverable Mutual Exclusion.” 40th ACM Symposium on Principles of Distributed Computing (PODC), 533–543. ACM (2021).

G. Giakkoupis, M. J. Giv and P. Woelfel. “Efficient randomized DCAS.” Proceedings of the 53rd ACM Symposium on Theory of Computing (STOC), 1221–1234. ACM (2021).

F. Ellen, R. Gelashvili, P. Woelfel and L. Zhu. “Space Lower Bounds for the Signal Detection Problem.” Theory of Computing Systems 65(4): 687–705 (2021).

D. Y. C. Chan and P. Woelfel. “Recoverable Mutual Exclusion with Constant Amortized RMR Complexity from Standard Primitives.” 39th ACM Symposium on Principles of Distributed Computing (PODC), 181–190. ACM (2020).

S. Ovens and P. Woelfel. “Strongly Linearizable Implementations of Snapshots and Other Types.” 38th ACM Symposium on Principles of Distributed Computing (PODC), 197–206. ACM (2019).

Z. Aghazadeh, D. Imbs, M. Raynal, G. Taubenfeld and P. Woelfel. “Optimal Memory-Anonymous Symmetric Deadlock-Free Mutual Exclusion.” 38th ACM Symposium on Principles of Distributed Computing (PODC), 157–166. ACM (2019).

P. Woelfel. “Towards a Theory of Randomized Shared Memory Algorithms.” 38th ACM Symposium on Principles of Distributed Computing (PODC), 156. ACM (2019).

G. Giakkoupis and P. Woelfel. “Efficient Randomized Test-And-Set Implementations.” Distributed Computing: 1–22. Springer (2019). Invited to the special issue of PODC 2012.

F. Ellen, R. Gelashvili, P. Woelfel and L. Zhu. “Space Lower Bounds for the Signal Detection Problem.” 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, 26:1–26:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019).

A. Eghbali and P. Woelfel. “An Almost Tight RMR Lower Bound for Abortable Test-And-Set.” Distributed Computing - 32nd International Symposium (DISC), 21:1–21:19. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018).

J. Aspnes, B. Haeupler, A. Tong and P. Woelfel. “Allocate-On-Use Space Complexity of Shared-Memory Algorithms.” Distributed Computing - 32nd International Symposium (DISC), 8:1–8:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018).

G. Giakkoupis and P. Woelfel. “An Improved Bound for Random Binary Search Trees with Concurrent Insertions.” 35th International Symposium on Theoretical Aspects of Computer Science, STACS 2018, 37:1–37:13 (2018).

G. Giakkoupis and P. Woelfel. “Randomized Abortable Mutual Exclusion with Constant Amortized RMR Complexity on the CC Model.” 36th ACM Symposium on Principles of Distributed Computing (PODC), 221–229. ACM (2017).

Z. Aghazadeh and P. Woelfel. “Upper Bounds for Boundless Tagging with Bounded Objects.” Distributed Computing - 30th International Symposium (DISC), 442–457 (2016).

O. Denysyuk and P. Woelfel. “Are Shared Objects Composable under an Oblivious Adversary?” 35th ACM Symposium on Principles of Distributed Computing (PODC), 335–344 (2016).

G. Giakkoupis, Y. Nazari and P. Woelfel. “How Asynchrony Affects Rumor Spreading Time.” 35th ACM Symposium on Principles of Distributed Computing (PODC), 185–194 (2016).

O. Denysyuk and P. Woelfel. “Wait-Freedom is Harder than Lock-Freedom under Strong Linearizability.” Distributed Computing - 29th International Symposium (DISC), 60–74. Springer (2015).

H. Attiya, D. Hendler and P. Woelfel. “Trading Fences with RMRs and Separating Memory Models.” 34th ACM Symposium on Principles of Distributed Computing (PODC), 173–182. ACM (2015).

Z. Aghazadeh and P. Woelfel. “On the Time and Space Complexity of ABA Prevention and Detection.” 34th ACM Symposium on Principles of Distributed Computing (PODC), 193–202. ACM (2015).

G. Giakkoupis, M. Helmi, L. Higham and P. Woelfel. “Test-and-Set in Optimal Space.” Proceedings of the 47th ACM Symposium on Theory of Computing (STOC), 615–623. ACM (2015).

Z. Aghazadeh and P. Woelfel. “Space- and Time-Efficient Long-Lived Test-And-Set Objects.” Principles of Distributed Systems - 18th International Conference, OPODIS 2014, 404–419. Springer (2014).

M. Helmi, L. Higham and P. Woelfel. “Space Bounds for Adaptive Renaming.” Distributed Computing - 28th International Symposium (DISC), 303–317. Springer (2014).

G. Giakkoupis and P. Woelfel. “Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM.” 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, 504–513. IEEE Computer Society (2014).

M. Aumüller, M. Dietzfelbinger and P. Woelfel. “Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash.” Algorithmica 70(3): 428–456. Springer (2014). Special Issue on ESA 2012 (invited).

M. Elahi, C. Williamson and P. Woelfel. “Turbocharged Speed Scaling: Analysis and Evaluation.” 22nd International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), 41–50. IEEE Computer Society (2014).

Z. Aghazadeh, W. Golab and P. Woelfel. “Making Objects Writable.” 33rd ACM Symposium on Principles of Distributed Computing (PODC), 385–395. ACM (2014).

M. Elahi, C. Williamson and P. Woelfel. “Decoupled Speed Scaling: Analysis and Evaluation.” Performance Evaluation 73: 3–17. Elsevier (2014). Special Issue on QEST 2012 (invited).

M. Helmi, L. Higham, E. Pacheco and P. Woelfel. “The Space Complexity of Long-Lived and One-Shot Timestamp Implementations.” Journal of the ACM 61(1): 7:1–7:25. ACM (2014). Special Issue on PODC 2011 (invited).

M. Dietzfelbinger and P. Woelfel. “Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids.” Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, 816–829 (2014).

F. Ellen and P. Woelfel. “An Optimal Implementation of Fetch-and-Increment.” Distributed Computing - 27th International Symposium (DISC), 284–298. Springer (2013).

G. Giakkoupis, A.-M. Kermarrec and P. Woelfel. “Gossip Protocols for Renaming and Sorting.” Distributed Computing - 27th International Symposium (DISC), 194–208. Springer (2013).

G. Giakkoupis, M. Helmi, L. Higham and P. Woelfel. “An \(O(\sqrt n)\) Space Bound for Obstruction-Free Leader Election.” Distributed Computing - 27th International Symposium (DISC), 46–60. Springer (2013).

D. Alistarh, J. Aspnes, G. Giakkoupis and P. Woelfel. “Randomized Loose Renaming in \(O(\log\log n)\) Time.” 32nd ACM Symposium on Principles of Distributed Computing (PODC), 200–209. ACM (2013).

Z. Aghazadeh, W. Golab and P. Woelfel. “Brief Announcement: Resettable Objects and Efficient Memory Reclamation for Concurrent Algorithms.” 32nd ACM Symposium on Principles of Distributed Computing (PODC), 322–324. ACM (2013).

B. M. Elahi, C. Williamson and P. Woelfel. “Meeting the fairness deadline in speed scaling systems: is turbocharging enough?” SIGMETRICS Performance Evaluation Review 40(3): 89–91. ACM SIGMETRICS (2012).

F. Ellen, V. Ramachandran and P. Woelfel. “Efficient Fetch-and-Increment.” Distributed Computing - 26th International Symposium (DISC), 16–30. Springer (2012).

A. Pareek and P. Woelfel. “RMR-Efficient Randomized Abortable Mutual Exclusion.” Distributed Computing - 26th International Symposium (DISC), 267–281. Springer (2012).

M. Aumüller, M. Dietzfelbinger and P. Woelfel. “Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash.” Algorithms - ESA 2012 - 20th Annual European Symposium, 108–120. Springer (2012).

M. Elahi, C. Williamson and P. Woelfel. “Decoupled Speed Scaling: Analysis and Evaluation.” 9th International Conference on Quantitative Evaluation of Systems, QEST 2012, 2–12. IEEE Computer Society (2012). Best paper award.

G. Giakkoupis and P. Woelfel. “On the Time and Space Complexity of Randomized Test-And-Set.” 31st ACM Symposium on Principles of Distributed Computing (PODC), 19–28. ACM (2012). Best paper award.

M. Helmi, L. Higham and P. Woelfel. “Strongly Linearizable Implementations: Possibilities and Impossibilities.” 31st ACM Symposium on Principles of Distributed Computing (PODC), 385–394. ACM (2012).

G. Giakkoupis and P. Woelfel. “Brief Announcement: A Tight RMR Lower Bound for Randomized Mutual Exclusion.” 31st ACM Symposium on Principles of Distributed Computing (PODC), 239–240. ACM (2012).

G. Giakkoupis and P. Woelfel. “A Tight RMR Lower Bound for Randomized Mutual Exclusion.” Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), 983–1002. ACM (2012).

W. Golab, D. Hendler, V. Hadzilacos and P. Woelfel. “RMR-efficient implementations of comparison primitives using read and write operations.” Distributed Computing 25(2): 109–162. Springer (2012). Invited to the special issue of PODC 2007.

T. Q. Klassen and P. Woelfel. “Independence of Tabulation-Based Hash Classes.” LATIN 2012: Theoretical Informatics - number Latin American Symposium, 506–517. Springer (2012).

G. Giakkoupis, T. Sauerwald, H. Sun and P. Woelfel. “Low Randomness Rumor Spreading via Hashing.” 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, 314–325. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2012).

A. Brodsky, F. Ellen and P. Woelfel. “Fully-adaptive algorithms for long-lived renaming.” Distributed Computing 24(2): 119–134. Springer (2011).

D. Hendler and P. Woelfel. “Randomized Mutual Exclusion with Sub-Logarithmic RMR-Complexity.” Distributed Computing 24(1): 3–19. Springer (2011). Special Issue on PODC 2009 (invited).

M. Helmi, L. Higham, E. Pacheco and P. Woelfel. “The Space Complexity of Long-Lived and One-Shot Timestamp Implementations.” 30th ACM Symposium on Principles of Distributed Computing (PODC), 139–148. ACM (2011). Best paper award.

W. Golab, L. Higham and P. Woelfel. “Linearizable Implementations Do Not Suffice for Randomized Distributed Computation.” Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC), 373–382. ACM (2011).

M. Dietzfelbinger, J. E. Rowe, I. Wegener and P. Woelfel. “Precision, Local Search and Unimodal Functions.” Algorithmica 59(3): 301–322. Springer (2011). Special Issue: Theory of Evolutionary Computation (invited).

George Giakkoupis and P. Woelfel. “On the Randomness Requirements of Rumor Spreading.” Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, 449–461. SIAM (2011).

P. Beame, M. David, T. Pitassi and P. Woelfel. “Separating Deterministic from Randomized Multiparty Communication Complexity.” Theory of Computing 6(1): 201–225. Theory of Computing (2010).

M. Dietzfelbinger, J. E. Rowe, I. Wegener and P. Woelfel. “Tight Bounds for Blind Search on the Integers and the Reals.” Combinatorics, Probability and Computing 19(5): 711–728. Cambridge Journals (2010).

D. Hendler and P. Woelfel. “Adaptive Randomized Mutual Exclusion in Sub-Logarithmic Expected Time.” 29th ACM Symposium on Principles of Distributed Computing (PODC), 141–150. ACM (2010).

W. Golab, D. Hendler and P. Woelfel. “An \(O(1)\) RMRs Leader Election Algorithm.” SIAM Journal on Computing 39(7): 2726–2760. Society for Industrial; Applied Mathematics (2010).

D. Hendler and P. Woelfel. “Randomized Mutual Exclusion in \(O(\log N/\log\log N)\) RMRs.” 28th ACM Symposium on Principles of Distributed Computing (PODC), 26–35. ACM (2009).

M. Dietzfelbinger and P. Woelfel. “Brief Announcement: Tight Lower Bounds for Greedy Routing in Uniform Small World Rings.” 28th ACM Symposium on Principles of Distributed Computing (PODC), 300–301. ACM (2009).

M. Dietzfelbinger and P. Woelfel. “Tight Lower Bounds for Greedy Routing in Uniform Small World Rings.” Proceedings of the 41st ACM Symposium on Theory of Computing (STOC), 591–600. ACM (2009).

R. Nunkesser and P. Woelfel. “Representation of graphs by OBDDs.” Discrete Applied Mathematics 157(2): 247–261. Elsevier (2009).

H. Attiya, D. Hendler and P. Woelfel. “Brief Announcement: Tight RMR Lower Bounds for Mutual Exclusion and Other Problems.” 27th ACM Symposium on Principles of Distributed Computing (PODC), 447. ACM (2008).

M. Dietzfelbinger, J. E. Rowe, I. Wegener and P. Woelfel. “Precision, Local Search and Unimodal Functions.” Genetic and Evolutionary Computation Conference, GECCO 2008, Proceedings, 771–778. ACM (2008). Best paper award, formal theory track.

H. Attiya, D. Hendler and P. Woelfel. “Tight RMR Lower Bounds for Mutual Exclusion and Other Problems.” Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), 217–226. ACM (2008).

M. Dietzfelbinger, J. E. Rowe, I. Wegener and P. Woelfel. “Tight Bounds for Blind Search on the Integers.” 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008, 241–252. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2008).

I. Wegener and P. Woelfel. “New Results on the Complexity of the Middle Bit of Multiplication.” Computational Complexity 16(3): 298–323. Springer (2007).

Wojciech Golab, V. Hadzilacos, D. Hendler and P. Woelfel. “Constant-RMR Implementations of CAS and Other Synchronization Primitives Using Read and Write Operations.” 26th ACM Symposium on Principles of Distributed Computing (PODC), 3–12. ACM (2007).

P. Beame, M. David, T. Pitassi and P. Woelfel. “Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.” Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, 134–145. Springer (2007).

B. Bollig, S. Waack and P. Woelfel. “Parity Graph-Driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.” Theoretical Computer Science 362: 86–99. Elsevier (2006).

P. Woelfel. “A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs.” Theoretical Computer Science 363(1): 76–84. Elsevier (2006). Special Issue COCOON 2004 (invited).

A. Brodsky, F. Ellen and P. Woelfel. “Fully Adaptive Algorithms for Long-Lived Renaming.” Distributed Computing - 20th International Symposium (DISC), 413–427. Springer (2006).

P. Woelfel. “Maintaining External Memory Efficient Hash Tables.” 10th International Workshop on Randomization and Computation, 508–519. Springer (2006).

W. Golab, D. Hendler and P. Woelfel. “An \(O(1)\) RMRs Leader Election Algorithm.” 25th ACM Symposium on Principles of Distributed Computing (PODC), 238–247. ACM (2006).

P. Woelfel. “Symbolic Topological Sorting with OBDDs.” Journal of Discrete Algorithms 4(1): 51–71. Elsevier (2006).

P. Woelfel. “Asymmetric Balanced Allocation with Simple Hash Functions.” Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, 424–434. ACM (2006).

R. Nunkesser and P. Woelfel. “Representation of Graphs by OBDDs.” Algorithms and Computation, 16th International Symposium, ISAAC 2005, 1132–1142. Springer (2005).

P. Woelfel. “Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.” Journal of Computer and System Sciences 71(4): 520–534. Elsevier (2005).

B. Bollig and P. Woelfel. “A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications.” Theory of Computing Systems 38(6): 671–685. Springer (2005).

I. Wegener and P. Woelfel. “New Results on the Complexity of the Middle Bit of Multiplication.” 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 100–110. IEEE Computer Society (2005).

P. Woelfel. “A Construction Method for Optimally Universal Hash Families and its Consequences for the Existence of RBIBDs.” Computing and Combinatorics, 10th Annual International Conference, COCOON 2004, 23–32. Springer (2004).

P. Woelfel. “Symbolic Topological Sorting with OBDDs.” Mathematical Foundations of Computer Science 2003, 28th International Symposium, 671–680. Springer (2003).

M. Sauerhoff and P. Woelfel. “Time-Space Tradeoff Lower Bounds for Integer Multiplication and Graphs of Arithmetic Functions.” Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), 186–195. ACM (2003).

M. Dietzfelbinger and P. Woelfel. “Almost Random Graphs with Simple Hash Functions.” Proceedings of the 35th ACM Symposium on Theory of Computing (STOC), 629–638. ACM (2003).

B. Bollig, S. Waack and P. Woelfel. “Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication.” 2nd IFIP International Conference on Theoretical Computer Science (TCS 2002), 83–94. Kluwer (2002).

B. Bollig and P. Woelfel. “A Lower Bound Technique for Nondeterministic Graph-Driven Read-Once-Branching Programs and its Applications.” Mathematical Foundations of Computer Science 2002, 27th International Symposium, 131–142. Springer (2002).

P. Woelfel. “On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism.” 17th Annual IEEE Conference on Computational Complexity (CCC 2002), 80–89. IEEE Computer Society (2002).

P. Woelfel. “A Lower Bound Technique for Restricted Branching Programs and Applications.” 19th International Symposium on Theoretical Aspects of Computer Science, STACS 2002, 431–442. Springer (2002).

B. Bollig and P. Woelfel. “A Read-Once Branching Program Lower Bound of \(\Omega(2^{n/4})\) for Integer Multiplication Using Universal Hashing.” Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), 419–424. ACM (2001).

P. Woelfel. “New Bounds on the OBDD-Size of Integer Multiplication via Universal Hashing.” 18th International Symposium on Theoretical Aspects of Computer Science, STACS 2001, 563–574. Springer (2001).

P. Woelfel. “Efficient Strongly Universal and Optimally Universal Hashing.” Mathematical Foundations of Computer Science 1999, 24th International Symposium, 262–272. Springer (1999).