Homepage

Reto Spöhel

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 315
66123 Saarbrücken
Germany

Email: Get my email address via email
Phone: +49 681 9325 1015
Fax: +49 681 9325 1099

Research Interests

Threshold phenomena in random structures
Power-of-choices phenomena in random processes
Randomized algorithms
Combinatorial games

Publications

Submitted journal papers

Explosive percolation in Erdős-Rényi-like random graph processes (with Konstantinos Panagiotou, Angelika Steger, and Henning Thomas)
Submitted.
On balanced coloring games in random graphs (with Luca Gugelmann)
Submitted.

Papers in refereed conferences

Coloring random graphs online without creating monochromatic subgraphs (with Torsten Mütze and Thomas Rast)
Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), PR 137, 145-158.
Explosive percolation in Erdős-Rényi-like random graph processes (with Konstantinos Panagiotou, Angelika Steger, and Henning Thomas)
Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2011, ENDM 38, 699-704. [Preprint]
On balanced coloring games in random graphs (with Luca Gugelmann)
Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2011, ENDM 38, 425-430. [Preprint]
On the path-avoidance vertex-coloring game (with Torsten Mütze)
Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2011, ENDM 38, 657-662. [Preprint]
PAC learning and genetic programming (with Timo Kötzing and Frank Neumann)
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) 2011, 2091-2096. [Preprint]
Coloring the edges of a random graph without a monochromatic giant component (with Angelika Steger and Henning Thomas)
Proceedings of the European Conference on Combinatorics, Graph Theory and Applications (EuroComb) 2009, ENDM 34, 615-619. [Preprint]
Online vertex colorings of random graphs without monochromatic subgraphs (with Martin Marciniszyn)
Proceedings of the 18th annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07), PR 125, 486-493. [Preprint]
On Euclidean vehicle routing with allocation (with Jan Remy and Andreas Weißl)
Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS '07), LNCS 4619, 601-612. [Preprint]
Threshold functions for asymmetric Ramsey properties involving cliques (with Martin Marciniszyn, Jozef Skokan, and Angelika Steger)
Proceedings of the 10th International Workshop on Randomized Techniques in Computation (RANDOM '06), LNCS 4110, 462-474. [Preprint]
The online clique avoidance game on random graphs (with Martin Marciniszyn and Angelika Steger)
Proceedings of the 9th International Workshop on Randomized Techniques in Computation (RANDOM '05), LNCS 3624, 390-401. [Preprint]

Papers in refereed journals

Upper bounds on probability thresholds for asymmetric Ramsey properties (with Yoshiharu Kohayakawa and Mathias Schacht)
Random Structures and Algorithms, to appear.
Coloring random graphs online without creating monochromatic subgraphs (with Torsten Mütze and Thomas Rast)
Random Structures and Algorithms, to appear. [Computer program] [Extended arXiv version]
Probabilistic one-player Ramsey games via deterministic two-player games (with Michael Belfrage and Torsten Mütze)
SIAM Journal of Discrete Mathematics, to appear. [Computer-generated proofs] [Extended arXiv version]
Creating small subgraphs in Achlioptas processes with growing parameter (with Michael Krivelevich)
SIAM Journal of Discrete Mathematics 620(1), 670-686, 2012. [Preprint]
Small subgraphs in random graphs and the power of multiple choices (with Torsten Mütze and Henning Thomas)
Journal of Combinatorial Theory, Series B 101(4), 237-268, 2011. [Preprint]
On the path-avoidance vertex-coloring game (with Torsten Mütze)
The Electronic Journal of Combinatorics 18(1), P163, 2011. [Computer program]
Von Neumann and Newman poker with a flip of hand values (with Nicla Bernasconi and Julian Lorenz)
Discrete Mathematics 311(21), 2337-2345, 2011. [Preprint]
Online vertex-coloring games in random graphs (with Martin Marciniszyn)
Combinatorica 30(1), 105-123, 2010. [Preprint]
On Euclidean vehicle routing with allocation (with Jan Remy and Andreas Weißl)
Computational Geometry: Theory and Applications 43(4), 357-376, 2010. [Preprint]
Offline thresholds for Ramsey-type games on random graphs (with Michael Krivelevich and Angelika Steger)
Random Structures and Algorithms 36(1), 57-79, 2010. [Preprint]
Coloring the edges of a random graph without a monochromatic giant component (with Angelika Steger and Henning Thomas)
The Electronic Journal of Combinatorics 17(1), R133, 2010.
Asymmetric Ramsey properties of random graphs involving cliques (with Martin Marciniszyn, Jozef Skokan, and Angelika Steger)
Random Structures and Algorithms 34(4), 419-453, 2009. [Preprint]
Online Ramsey games in random graphs (with Martin Marciniszyn and Angelika Steger)
Combinatorics, Probability and Computing 18(1-2), 271-300, 2009. [Preprint]
Upper bounds for online Ramsey games in random graphs (with Martin Marciniszyn and Angelika Steger)
Combinatorics, Probability and Computing 18(1-2), 259-270, 2009. [Preprint]
Balanced online Ramsey games in random graphs (with Anupam Prakash and Henning Thomas)
The Electronic Journal of Combinatorics 16(1), R11, 2009.

PhD thesis

On the power of choices in random graph processes, ETH Zurich, 2010.

Teaching

Courses taught:

Optimization (Summer 2012, joint with Rob van Stee)
Basic Mathematical Techniques for Computer Scientists (Summer 2012, joint with Timo Kötzing, Xavier Pérez Giménez, Chandan Saha, Thomas Sauerwald, Jens M. Schmidt, and Carola Winzen)
Grundzüge von Algorithmen und Datenstrukturen (Winter 2011/12, joint with Benjamin Doerr)
Advanced Randomized Methods in Computer Science (Block course Winter 2011/12, joint with Benjamin Doerr, Konstantinos Panagiotou, and Thomas Sauerwald)
Graph Theory (Summer 2011, joint with Benjamin Doerr and Danny Hermelin)
Models of Computation (Winter 2010/11, joint with Kurt Mehlhorn and Konstantinos Panagiotou)
Randomized Algorithms and Probabilistic Methods (Fall 2009, at ETH Zurich)

For an overview of my teaching activities as a PhD student see my old page at ETH Zurich.

Other Activities

Co-organizer of ALGO 2011

Short CV

April 2010 - present:
Postdoc at the Max Planck Institute for Informatics, Saarbrücken, Germany
December 2005 - February 2010:
Ph.D. in Computer Science in the Combinatorial Structures and Algorithms Group at ETH Zurich, Switzerland
Thesis: On the power of choices in random graph processes
Supervisor: Angelika Steger
October 2000 - April 2005:
Diploma in Mathematics (with distinction), ETH Zurich, Switzerland
January 2000:
Matura, Kantonsschule Frauenfeld, Switzerland

Private

Hobbies, interests

games of all kinds (board, cards, computer, mathematical, ...)
music (I sing in the university choir)
hiking
languages, literature, theatre
...