Yannic Maus, PhD student
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 )
Teaching:
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
Studienstiftung des Deutschen Volkes
Dean's List Mathematics, RWTH Aachen
Dean's List Computer Science, RWTH Aachen
Schöneborn-Preis 2013
NRW Stipendium, Deutschlandstipendium
Publications
Years: 2016 |
2015 | show all Conference papers Dan Hefetz, Fabian Kuhn, Yannic Maus, Angelika StegerPolynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model 2016 30th International Symposium on DIStributed Computing (DISC), Paris, September 26-30, 2016 » show abstract « hide abstract Abstract We show an Omega(\Delta^{\frac{1}{3}-\frac{\eta}{3}}) lower bound on the runtime of any deterministic distributed O(\Delta^{1+\eta})-graph coloring algorithm in a weak variant of the LOCAL model.
In particular, given a network graph G=(V,E), in the weak LOCAL model nodes communicate in synchronous rounds and they can use unbounded local computation. The nodes have no identifiers, but instead, the computation starts with an initial valid vertex coloring. A node can broadcast a single message of unbounded size to its neighbors and receives the set of messages sent to it by its neighbors.
The proof uses neighborhood graphs and improves their understanding in general such that it might help towards finding a lower (runtime) bound for distributed graph coloring in the standard LOCAL model. Fabian Kuhn, Sebastian Daum, Yannic MausRumor Spreading with Bounded In-Degree 2016 23rd Int. Coll. on Structural Information and Communication Complexity (SIROCCO), Helsinki, Finland » show abstract « hide abstract Abstract In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes.
In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'.
We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network. Conference papers Fabian Kuhn, Sebastian Daum, Yannic MausBrief Announcement: Rumor Spreading with Bounded In-Degree 2015 26th Int. Symp. on Distributed Computing (DISC), Tokyo, Japan » show abstract « hide abstract Abstract In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes.
In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'.
We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network.