# Yannic Maus

## Contact Details

NameYannic Maus |
||

Affiliation |
||

Location |
||

## Pubs By Year |
||

## Pub CategoriesComputer Science - Distributed; Parallel; and Cluster Computing (2) Mathematics - Functional Analysis (1) Computer Science - Data Structures and Algorithms (1) Computer Science - Networking and Internet Architecture (1) Computer Science - Discrete Mathematics (1) |

## Publications Authored By Yannic Maus

The algorithmic small-world phenomenon, empirically established by Milgram's letter forwarding experiments from the 60s, was theoretically explained by Kleinberg in 2000. However, from today's perspective his model has several severe shortcomings 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. Read More

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 $(\Delta+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(\sqrt{\log 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. Read More

We show an $\Omega\big(\Delta^{\frac{1}{3}-\frac{\eta}{3}}\big)$ lower bound on the runtime of any deterministic distributed $\mathcal{O}\big(\Delta^{1+\eta}\big)$-graph coloring algorithm in a weak variant of the \LOCAL\ model. In particular, given a network graph \mbox{$G=(V,E)$}, in the weak \LOCAL\ model nodes communicate in synchronous rounds and they can use unbounded local computation. We assume that the nodes have no identifiers, but that instead, the computation starts with an initial valid vertex coloring. Read More

A bounded, Riemann integrable and measurable set $K\subset \mathbb{R}^d$, which fulfills \[\sum\limits_{\gamma\in\Gamma}\mathbb{1}_K(x-\gamma)=k\text{ almost everywhere, $x\in\mathbb{R}^d$}\] for a lattice $\Gamma\subset\mathbb{R}^d$ is called $k$-tiling. If $K\subset\mathbb{R}^d$ is $k$-tiling $L^2(K)$ will admit a Riesz basis of exponentials. We use this result to construct generalized Riesz wavelet bases of $L^2(\mathbb{R}^2)$, arising from the action of suitable subsets of the affine group. Read More

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. Read More