Algorithms and Complexity

Yannic Maus, PhD student

Yannic Maus

Contact Information:
  • Address · Albert-Ludwigs-Universität, Institut für Informatik, Georges-Köhler-Allee 106, D - 79110 Freiburg
  • Room · 106-00-005
  • Phone · +49 761 - 203 67415
  • Fax · +49 761 - 203 67412
  • Email · Email: Yannic.Maus@cs.uni-freiburg.de

Research Interests:
I am mainly interested in the local nature of distributed problems, e.g., lower bounds for (Delta+1)-coloring algorithms in the LOCAL model. Besides I am interested in all kinds of classical graph problems (e.g. MIS, Coloring, VC, Matching) in the distributed setting.

Bachelor/Master Thesis:
I offer Bachelor/Master theses in the area of distributed algorithms. Chapter 1 in these lecture notes provides a basic introduction to distributed algorithms and it will show you how amazing this area can be (you will most likely see the fastest non trivial algorithm you will ever encounter!). A strong background in algorithms and mathematics is needed. If you are interested feel free to contact me (per email). A (cryptic) list of possible topics is attached:
  • Rumor Spreading with Bounded In-Degree.
  • The Structure of Neighborhood Graphs (for Multiple Rounds)
    (for the definition of (1 round) neighborhood graphs see e.g. Kuhn)

Completeted Bachelor/Master Theses/Projects:
  • Janosch Deurer - Complexity in the SLOCAL Model (Randomized vs. Deterministic)
  • Simon Weidner - Complexity in the SLOCAL Model (Completeness of Set Cover)
  • Pius Friedrich Meinert - Weak Distributed Symmetry Breaking Primitives
  • Ganindu Prabhashana - Bounded Gossip Interaction Protocols


Degrees and Titles:

  • January 2014 · MSc in Mathematics, RWTH Aachen, Germany
  • March 2013 · BSc in Mathematics, RWTH Aachen, Germany
  • July 2011 · BSc in Computer Science, RWTH Aachen, Germany

Scholarships and Awards:

  • Best Paper Award: SIROCCO 2016, DISC 2016, DISC 2017
  • Studienstiftung des Deutschen Volkes
  • Dean's List Mathematics, RWTH Aachen
  • Dean's List Computer Science, RWTH Aachen
  • Schöneborn-Preis 2013
  • NRW Stipendium, Deutschlandstipendium


Years: 2017 | 2016 | 2015


    Conference papers
    • Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman Molla
      Greedy Routing and the Algorithmic Small-World Phenomenon
      2017 Principles of Distributed Computing (PODC), July 25-27, 2017, Washington, DC, USA
    • Mohsen Ghaffari, Juho Hirvonnen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara Uitto,
      Improved Distributed Degree Splitting and Edge Coloring
      2017 International Symposium on DIStributed Computing (DISC) 2017
    • Mohsen Ghaffari, Fabian Kuhn, Yannic Maus
      On the Complexity of Local Distributed Graph Problems
      2017 ACM Symposium on Theory of Computing (STOC) 2017.


    Conference papers
    • Dan Hefetz, Fabian Kuhn, Yannic Maus, Angelika Steger
      Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
      2016 30th International Symposium on DIStributed Computing (DISC), Paris, September 26-30, 2016
    • Fabian Kuhn, Sebastian Daum, Yannic Maus
      Rumor Spreading with Bounded In-Degree
      2016 23rd Int. Coll. on Structural Information and Communication Complexity (SIROCCO), Helsinki, Finland


    Conference papers
    • Fabian Kuhn, Sebastian Daum, Yannic Maus
      Brief Announcement: Rumor Spreading with Bounded In-Degree
      2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan