Dr. Yannic Maus
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:
Simon Weidner - Ruling Edge Sets in Graphs and Hypergraphs
Tobias Grugel - Deterministic Sublinear-Time Distributed Coloring in the CONGEST Model
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
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 , 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
Publications
Years: 2019 |
2018 |
2017 |
2016 |
2015 | show all Conference papers Philipp Bamberger, Fabian Kuhn, Yannic MausLocal Distributed Algorithms in Highly Dynamic Networks 2019 33rd IEEE Int. Parallel and Distributed Processing Symposium (IPDPS) » show abstract « hide abstract Abstract We define a generalization of local distributed graph problems to (synchronous round-based) dynamic networks and present a framework for developing algorithms for these problems. The algorithms should satisfy non-trivial guarantees in every round. The guarantees should be stronger the more stable the graph has been during the last few rounds and coincide with the definition of the static graph problem if no topological change appeared recently. Moreover, if only a constant neighborhood around some part of the graph is stable during an interval, the algorithms should quickly converge to a solution for this part of the graph that remains unchanged throughout the interval.
We demonstrate our generic framework with two classic distributed graph problems, namely (degree+1)-vertex coloring and maximal independent set (MIS). To illustrate the given guarantees consider the vertex coloring problem: Any conflict between two nodes caused by a newly inserted edge is resolved within T = O(log n) rounds. During this conflict resolving both nodes always output colors that are not in conflict with their respective ‘old‘ neighbors. The largest color that a node is allowed to output is determined by the number of distinct neighbors that it has seen in the last T rounds. Conference papers Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Juho HirvonenImproved Distributed Delta-Coloring 2018 ACM Symposium on Principles of Distributed Computing (PODC) » show abstract « hide abstract Abstract We present a randomized distributed algorithm that computes a $\Delta$-coloring in any non-complete graph with maximum degree $\Delta \geq 4$ in $O(\log \Delta) + 2^{O(\sqrt{\log\log n})}$ rounds, as well as a randomized algorithm that computes a $\Delta$-coloring in $O((\log \log n)^2)$ rounds when $\Delta \in [3, O(1)]$. Both these algorithms improve on an $O(\log^3 n/\log \Delta)$-round algorithm of Panconesi and Srinivasan~[STOC'1993], which has remained the state of the art for the past 25 years. Moreover, the latter algorithm gets (exponentially) closer to an $\Omega(\log\log n)$ round lower bound of Brandt et al.~[STOC'16]. Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, Jara UittoDeterministic Distributed Edge-Coloring with Fewer Colors 2018 50th ACM Symposium on Theory of Computing (STOC) » show abstract « hide abstract Abstract We present a deterministic distributed algorithm, in the $\LOCAL$ model, that computes a $(1+o(1))\Delta$-edge-coloring in polylogarithmic-time, so long as the maximum degree $\Delta=\tilde{\Omega}(\log n)$. For smaller $\Delta$, we give a polylogarithmic-time $3\Delta/2$-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of $2\Delta-1$ colors, and they improve significantly on the recent polylogarithmic-time $(2\Delta-1)(1+o(1))$-edge-coloring of Ghaffari and Su [SODA'17] and the $(2\Delta-1)$-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS'17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes. Fabian Kuhn, Yannic Maus, Simon WeidnerDeterministic Distributed Ruling Sets of Line Graphs 2018 Int. Coll. on Structural Information and Communication Complexity (SIROCCO) » show abstract « hide abstract Abstract An $(\alpha,\beta)$-ruling set of a graph $G=(V,E)$ is a set
$R\subseteq V$ such that for any node $v\in V$ there is a node
$u\in R$ in distance at most $\beta$ from $v$ and such that any two
nodes in $R$ are at distance at least $\alpha$ from each other. The
concept of ruling sets can naturally be extended to edges, i.e., a
subset $F\subseteq E$ is an \emph{$(\alpha,\beta)$-ruling edge set}
of a graph $G=(V,E)$ if the corresponding nodes form an
$(\alpha,\beta)$-ruling set in the line graph of $G$. This paper
presents a simple deterministic, distributed algorithm, in the
CONGEST ~ model, for computing $(2,2)$-ruling edge sets in
$O(\logstar n)$ rounds. Furthermore, we extend the algorithm to
compute ruling sets of graphs with bounded \emph{diversity}. Roughly
speaking, the diversity of a graph is the maximum number of maximal
cliques a vertex belongs to. We devise $(2,O(\diversity))$-ruling
sets on graphs with diversity $\diversity$ in
$O(\diversity+\logstar n)$ rounds. This also implies a fast,
deterministic $(2,O(\rank))$-ruling edge set algorithm for
hypergraphs with rank at most \rank.
Furthermore, we provide a ruling set algorithm for general graphs
that for any $B\geq 2$ computes an
$\big(\alpha, \alpha \ceil{\log_B n}\big)$-ruling set in
$O(\alpha \cdot B \cdot \log_B n)$ rounds in the CONGEST
model. The algorithm can be modified to compute a
$\big(2, \beta \big)$-ruling set in
$O(\beta \degree^{2/\beta} + \logstar n)$ rounds in the
CONGEST model, which matches the currently best known such algorithm
in the more general LOCAL model. Conference papers Karl Bringmann, Ralph Keusch, Johannes Lengler, Yannic Maus, Anisur Rahaman MollaGreedy Routing and the Algorithmic Small-World Phenomenon 2017 36th ACM Symposium on Principles of Distributed Computing (PODC) » show abstract « hide abstract Abstract The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s~\cite{milgram1967small}, was theoretically explained by Kleinberg in 2000~\cite{KleinbergModel}. However, from today's perspective his model has several severe
shortcomings
%drawbacks
that limit the applicability to real-world networks.
In order to give a more convincing explanation of the algorithmic small-world phenomenon, we study decentralized greedy routing in a more flexible random graph model (geometric inhomogeneous random graphs) which overcomes all previous shortcomings.
%has not only theoretically good properties,
Apart from exhibiting good properties in theory, it has also been extensively experimentally validated that this model reasonably captures real-world networks.
In this model, the greedy routing protocol is purely distributed as each vertex only needs to know information about its direct neighbors. We prove that it succeeds with constant probability, and in case of success almost surely finds an almost shortest path of length $\Theta(\log\log n)$, where our bound is tight including the leading constant.
Moreover, we study natural local patching methods which augment greedy routing by backtracking and which do not require any global knowledge. We show that such methods can ensure success probability 1 in an asymptotically tight number of steps.
These results also address the question of Krioukov et al.~\cite{krioukov2007compact} whether there are efficient local routing protocols for the internet graph. There were promising experimental studies, but the question remained unsolved theoretically. Our results give for the first time a rigorous and analytical affirmative answer. Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, Jara UittoImproved Distributed Degree Splitting and Edge Coloring 2017 International Symposium on DIStributed Computing (DISC) » show abstract « hide abstract Abstract The degree splitting problem requires coloring the edges of a graph red or blue such that each node has almost the same number of edges in each color, up to a small additive discrepancy. The directed variant of the problem requires orienting the edges such that each node has almost the same number of incoming and outgoing edges, again up to a small additive discrepancy.
We present deterministic distributed algorithms for both variants, which improve on their counterparts presented by Ghaffari and Su [SODA'17]: our algorithms are significantly simpler and faster, and have a much smaller discrepancy. This also leads to a faster and simpler deterministic algorithm for $(2+o(1))\Delta$-edge-coloring, improving on that of Ghaffari and Su. Mohsen Ghaffari, Fabian Kuhn, Yannic MausOn the Complexity of Local Distributed Graph Problems 2017 ACM Symposium on Theory of Computing (STOC) » show abstract « hide abstract Abstract This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2^(O(log(sqrt(n))). Understanding and narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in log^(O(1))n rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and (Δ+1)-coloring) in log^(O(1))n rounds in the LOCAL model. We show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values. 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.