Publications

2023

David Yu Cheng Chan, George Giakkoupis and Philipp Woelfel.
Word-size RMR tradeoffs for recoverable mutual exclusion.
Proc. 42nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 79-89, Jun. 19-23 2023.
🏆Best paper  award.
[pdf]

George Giakkoupis and Isabella Ziccardi.
Distributed self-stabilizing MIS with few states and weak communication.
Proc. 42nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 310-320, Jun. 19-23 2023.
[pdf]

2022

George Giakkoupis.
Simple efficient distributed processes on graphs.
Keynote Talk 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Jun. 29-29 2022.
[pdf]

George Giakkoupis.
Expanders via local edge flips in quasilinear time.
Proc. 54th ACM Symposium on Theory of Computing (STOC), pp. 64-76, Jun. 20-24 2022.
[pdf]

2021

Andrea E. F. Clementi, Francesco D'Amore, George Giakkoupis and Emanuele Natale.
Search via parallel Lévy walks on Z^2.
Proc. 40th ACM Symposium on Principles of Distributed Computing (PODC), pp. 81-91, Jul. 26-30 2021.
[pdf]

George Giakkoupis, Mehrdad Jafari Giv and Philipp Woelfel.
Efficient randomized DCAS.
Proc. 53rd ACM Symposium on Theory of Computing (STOC), pp. 1221-1234, Jun. 21-25 2021.
[pdf]

Paul Bastide, George Giakkoupis and Hayk Saribekyan.
Self-stabilizing clock synchronization with 1-bit messages.
Proc. 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2154-2173, Jan. 10-13 2021.
[pdf] [talk]

2020

George Giakkoupis, Hayk Saribekyan and Thomas Sauerwald.
Spread of information and diseases via random walks in sparse graphs.
Proc. 34th International Symposium on Distributed Computing (DISC), pp. 9:1-9:17, Oct. 12-16 2020.
[pdf]

Petra Berenbrink, George Giakkoupis and Peter Kling.
Optimal time and space leader election in population protocols.
Proc. 52nd ACM Symposium on Theory of Computing (STOC), pp. 119-129, Jun. 22-26 2020.
[pdf] [talk]

2019

George Giakkoupis and Philipp Woelfel.
Efficient randomized test-and-set implementations.
Distributed Computing 32(6): 565-586, Dec. 2019.
[pdf]

George Giakkoupis, Frederik Mallmann-Trenn and Hayk Saribekyan.
How to spread a rumor: Call your neighbors or take a walk?
Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 24-33, Jul. 29-Aug. 2 2019.
[pdf]

2018

Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi and Alessandro Panconesi.
Rumor spreading and conductance.
Journal of the ACM (JACM) 65(4): 17:1-17:21, 2018.
[pdf]

George Giakkoupis and Philipp Woelfel.
An improved bound for random binary search trees with concurrent insertions.
Proc. 35th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 37:1-37:13, Feb. 28-Mar. 3 2018.
[pdf]

Petra Berenbrink, George Giakkoupis and Peter Kling.
Tight bounds for coalescing-branching random walks on regular graphs.
Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1715-1733, Jan. 7-10 2018.
[pdf]

2017

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler and Fabian Kuhn.
Tight bounds on vertex connectivity under sampling.
ACM Transactions on Algorithms 13(2): 19:1-19:26, Nov. 2017.
[pdf]

George Giakkoupis and Philipp Woelfel.
Randomized abortable mutual exclusion with constant amortized RMR complexity on the CC model.
Proc. 36th ACM Symposium on Principles of Distributed Computing (PODC), pp. 221-229, Jul. 25-27 2017.
[pdf]

2016

George Giakkoupis.
Amplifiers and suppressors of selection for the Moran process on undirected graphs.
Preprint, arXiv:1611.01585 [cs.DM], Nov. 5 2016.
[arXiv]

George Giakkoupis, Yasamin Nazari and Philipp Woelfel.
How asynchrony affects rumor spreading time.
Proc. 35th ACM Symposium on Principles of Distributed Computing (PODC), pp. 185-194, Jul. 25-29 2016.
[pdf]

Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec and Frederik Mallmann-Trenn.
Bounds on the voter model in dynamic networks.
Proc. 43rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 146:1-146:15, Jul. 12-15 2016.
[pdf]

Petra Berenbrink, Tom Friedetzky, George Giakkoupis and Peter Kling.
Efficient plurality consensus, or: The benefits of cleaning up from time to time.
Proc. 43rd International Colloquium on Automata, Languages and Programming (ICALP), pp. 136:1-136:14, Jul. 12-15 2016.
[pdf]

2015

George Giakkoupis, Rachid Guerraoui, Arnaud Jégou, Anne-Marie Kermarrec and Nupur Mittal.
Privacy-conscious information diffusion in social networks.
Proc. 29th International Symposium on Distributed Computing (DISC), pp. 480-496, Oct. 5-9 2015.
[pdf]

George Giakkoupis, Maryam Helmi, Lisa Higham and Philipp Woelfel.
Test-and-set in optimal space.
Proc. 47th ACM Symposium on Theory of Computing (STOC), pp. 615-623, Jun. 14-17 2015.
[pdf]

Keren Censor-Hillel, Mohsen Ghaffari, George Giakkoupis, Bernhard Haeupler and Fabian Kuhn.
Tight bounds on vertex connectivity under vertex sampling.
Proc. 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2006-1018, Jan. 4-6 2015.
[pdf]

2014

George Giakkoupis and Philipp Woelfel.
Randomized mutual exclusion with constant amortized RMR complexity on the DSM.
Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 504-513, Oct. 18-21 2014.
[pdf]

George Giakkoupis, Thomas Sauerwald and Alexandre Stauffer.
Randomized rumor spreading in dynamic graphs.
Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP), pp. 495-507, Jul. 7-11 2014.
[pdf]

Pierre Fraigniaud and George Giakkoupis.
Greedy routing in small-world networks with power-law degrees.
Distributed Computing 27(4): 231-253, 2014.
[pdf]

George Giakkoupis.
Tight bounds for rumor spreading with vertex expansion.
Proc. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 801-815, Jan. 5-7 2014.
[pdf]

2013

George Giakkoupis, Anne-Marie Kermarrec and Philipp Woelfel.
Gossip protocols for renaming and sorting.
Proc. 27th International Symposium on Distributed Computing (DISC), pp. 194-208, Oct. 14-18 2013.
[pdf] [podcast]

George Giakkoupis, Maryam Helmi, Lisa Higham and Philipp Woelfel.
An O(sqrt n) space bound for obstruction-free leader election.
Proc. 27th International Symposium on Distributed Computing (DISC), pp. 46-60, Oct. 14-18 2013.
[pdf]

Dan Alistarh, James Aspnes, George Giakkoupis and Philipp Woelfel.
Randomized loose renaming in O(loglog n) time.
Proc. 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 200-209, Jul. 22-24 2013.
[pdf]

2012

George Giakkoupis and Philipp Woelfel.
On the time and space complexity of randomized test-and-set.
Proc. 31st ACM Symposium on Principles of Distributed Computing (PODC), pp. 19-28, Jul. 16-18 2012.
🏆Best paper award.
[pdf]

George Giakkoupis and Philipp Woelfel.
A tight RMR lower bound for randomized mutual exclusion.
Proc. 44th ACM Symposium on Theory of Computing (STOC), pp. 983-1002, May 20-22 2012.
[pdf]

George Giakkoupis, Thomas Sauerwald, He Sun and Philipp Woelfel.
Low randomness rumor spreading via hashing.
Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 314-325, Feb. 29-Mar. 3 2012.
[pdf]

George Giakkoupis and Thomas Sauerwald.
Rumor spreading and vertex expansion.
Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1623-1641, Jan. 17-19 2012.
[pdf] [podcast]

2011

George Giakkoupis and Nicolas Schabanel.
Optimal path search in small worlds: Dimension matters.
Proc. 43rd ACM Symposium on Theory of Computing (STOC), pp. 393-402, June 6-8 2011.
[pdf]

George Giakkoupis.
Tight bounds for rumor spreading in graphs of a given conductance.
Proc. 28th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 57-68, Mar. 10-12 2011.
[pdf] [full-version] [poster]

George Giakkoupis and Philipp Woelfel.
On the randomness requirements of rumor spreading.
Proc. 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 449-461, Jan. 23-25 2011.
[pdf]

2010

Pierre Fraigniaud and George Giakkoupis.
On the bit communication complexity of randomized rumor spreading.
Proc. 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 134-143, June 13-15 2010.
[pdf]

Pierre Fraigniaud and George Giakkoupis.
On the searchability of small-world networks with arbitrary underlying structure.
Proc. 42nd ACM Symposium on Theory of Computing (STOC), pp. 389-398, June 6-8 2010.
[pdf]

2005-2009

Pierre Fraigniaud and George Giakkoupis.
The effect of power-law degrees on the navigability of small worlds.
Proc. 28th ACM Symposium on Principles of Distributed Computing (PODC), pp. 240-249, Aug. 10-12 2009.
[pdf] [full-version]

George Giakkoupis and Vassos Hadzilacos.
On the complexity of greedy routing in ring-based peer-to-peer networks.
Proc. 26th ACM Symposium on Principles of Distributed Computing (PODC), pp. 99-108, Aug. 12-15 2007.
[pdf] [see also Chapters 7&8 of my Thesis]

George Giakkoupis and Vassos Hadzilacos.
A scheme for load balancing in heterogeneous distributed hash tables.
Proc. 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 302-311, July 17-20 2005.
[pdf] [see also Chapters 2-6 of my Thesis]

Thesis

George Giakkoupis.
On load balancing and routing in peer-to-peer systems.
Ph.D. Thesis, Department of Computer Science, University of Toronto, Nov. 2008.
[pdf]