Publications

2018

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), Jan. 7-10 2018.
[pdf] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [full version] [bib]

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] [full version] [bib]

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

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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] [bib]

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 [<bib]

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] [bib]

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] [bib]

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] [bib]