BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yannic Maus

Yannic Maus appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingData Structures and AlgorithmsComputational Complexitymath.FA

Catalog footprint

What is connected

13works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Exponential Speedup Over Locality in MPC with Optimal Memory

Locally Checkable Labeling (LCL) problems are graph problems in which a solution is correct if it satisfies some given constraints in the local neighborhood of each node. Example problems in this class include maximal matching, maximal independent set, and coloring problems. A successful line of research has been studying the complexities of LCL problems on paths/cycles, trees, and general graphs, providing many interesting results for the LOCAL model of distributed computing. In this work, we initiate the study of LCL problems in the low-space Massively Parallel Computation (MPC) model. In particular, on forests, we provide a method that, given the complexity of an LCL problem in the LOCAL model, automatically provides an exponentially faster algorithm for the low-space MPC setting that uses optimal global memory, that is, truly linear. While restricting to forests may seem to weaken the result, we emphasize that all known (conditional) lower bounds for the MPC setting are obtained by lifting lower bounds obtained in the distributed setting in tree-like networks (either forests or high girth graphs), and hence the problems that we study are challenging already on forests. Moreover, the most important technical feature of our algorithms is that they use optimal global memory, that is, memory linear in the number of edges of the graph. In contrast, most of the state-of-the-art algorithms use more than linear global memory. Further, they typically start with a dense graph, sparsify it, and then solve the problem on the residual graph, exploiting the relative increase in global memory. On forests, this is not possible, because the given graph is already as sparse as it can be, and using optimal memory requires new solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Fast Distributed Vertex Splitting with Applications

We present ${\rm poly\log\log n}$-round randomized distributed algorithms to compute vertex splittings, a partition of the vertices of a graph into $k$ parts such that a node of degree $d(u)$ has $\approx d(u)/k$ neighbors in each part. Our techniques can be seen as the first progress towards general ${\rm poly\log\log n}$-round algorithms for the Lovász Local Lemma. As the main application of our result, we obtain a randomized ${\rm poly\log\log n}$-round CONGEST algorithm for $(1+ε)Δ$-edge coloring $n$-node graphs of sufficiently large constant maximum degree $Δ$, for any $ε>0$. Further, our results improve the computation of defective colorings and certain tight list coloring problems. All the results improve the state-of-the-art round complexity exponentially, even in the LOCAL model.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Near-Optimal Scheduling in the Congested Clique

This paper provides three nearly-optimal algorithms for scheduling $t$ jobs in the $\mathsf{CLIQUE}$ model. First, we present a deterministic scheduling algorithm that runs in $O(\mathsf{GlobalCongestion} + \mathsf{dilation})$ rounds for jobs that are sufficiently efficient in terms of their memory. The $\mathsf{dilation}$ is the maximum round complexity of any of the given jobs, and the $\mathsf{GlobalCongestion}$ is the total number of messages in all jobs divided by the per-round bandwidth of $n^2$ of the $\mathsf{CLIQUE}$ model. Both are inherent lower bounds for any scheduling algorithm. Then, we present a randomized scheduling algorithm which runs $t$ jobs in $O(\mathsf{GlobalCongestion} + \mathsf{dilation}\cdot\log{n}+t)$ rounds and only requires that inputs and outputs do not exceed $O(n\log n)$ bits per node, which is met by, e.g., almost all graph problems. Lastly, we adjust the \emph{random-delay-based} scheduling algorithm [Ghaffari, PODC'15] from the $\mathsf{CLIQUE}$ model and obtain an algorithm that schedules any $t$ jobs in $O(t / n + \mathsf{LocalCongestion} + \mathsf{dilation}\cdot\log{n})$ rounds, where the $\mathsf{LocalCongestion}$ relates to the congestion at a single node of the $\mathsf{CLIQUE}$. We compare this algorithm to the previous approaches and show their benefit. We schedule the set of jobs on-the-fly, without a priori knowledge of its parameters or the communication patterns of the jobs. In light of the inherent lower bounds, all of our algorithms are nearly-optimal. We exemplify the power of our algorithms by analyzing the message complexity of the state-of-the-art MIS protocol [Ghaffari, Gouleakis, Konrad, Mitrovic and Rubinfeld, PODC'18], and we show that we can solve $t$ instances of MIS in $O(t + \log\logΔ\log{n})$ rounds, that is, in $O(1)$ amortized time, for $t\geq \log\logΔ\log{n}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Classification of distributed binary labeling problems

We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable problems that can be encoded with an alphabet of size two in the edge labeling formalism. Examples of binary labeling problems include sinkless orientation, sinkless and sourceless orientation, 2-vertex coloring, perfect matching, and the task of coloring edges red and blue such that all nodes are incident to at least one red and at least one blue edge. More generally, we can encode e.g. any cardinality constraints on indegrees and outdegrees. We study the deterministic time complexity of solving a given binary labeling problem in trees, in the usual LOCAL model of distributed computing. We show that the complexity of any such problem is in one of the following classes: $O(1)$, $Θ(\log n)$, $Θ(n)$, or unsolvable. In particular, a problem that can be represented in the binary labeling formalism cannot have time complexity $Θ(\log^* n)$, and hence we know that e.g. any encoding of maximal matchings has to use at least three labels (which is tight). Furthermore, given the description of any binary labeling problem, we can easily determine in which of the four classes it is and what is an asymptotically optimal algorithm for solving it. Hence the distributed time complexity of binary labeling problems is decidable, not only in principle, but also in practice: there is a simple and efficient algorithm that takes the description of a binary labeling problem and outputs its distributed time complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distance-2 Coloring in the CONGEST Model

We give efficient randomized and deterministic distributed algorithms for computing a distance-$2$ vertex coloring of a graph $G$ in the CONGEST model. In particular, if $Δ$ is the maximum degree of $G$, we show that there is a randomized CONGEST model algorithm to compute a distance-$2$ coloring of $G$ with $Δ^2+1$ colors in $O(\logΔ\cdot\log n)$ rounds. Further if the number of colors is slightly increased to $(1+ε)Δ^2$ for some $ε>1/{\rm polylog}(n)$, we show that it is even possible to compute a distance-$2$ coloring deterministically in polylog$(n)$ time in the CONGEST model. Finally, we give a $O(Δ^2 + \log^* n)$-round deterministic CONGEST algorithm to compute distance-$2$ coloring with $Δ^2+1$ colors.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distributed Approximation on Power Graphs

We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^2$. While we focus mostly on exploring this theme in the distributed CONGEST model, we show new results and surprising connections to the centralized model of computation. In the CONGEST model, it is natural to expect that problems on $G^2$ would be quite difficult to solve efficiently on $G$, due to congestion. However, we show that the picture is both more complicated and more interesting. Specifically, we encounter two phenomena acting in opposing directions: (i) slowdown due to congestion and (ii) speedup due to structural properties of $G^2$. We demonstrate these two phenomena via two fundamental graph problems, namely, Minimum Vertex Cover (MVC) and Minimum Dominating Set (MDS). Among our many contributions, the highlights are the following. - In the CONGEST model, we show an $O(n/ε)$-round $(1+ε)$-approximation algorithm for MVC on $G^2$, while no $o(n^2)$-round algorithm is known for any better-than-2 approximation for MVC on $G$. - We show a centralized polynomial time $5/3$-approximation algorithm for MVC on $G^2$, whereas a better-than-2 approximation is UGC-hard for $G$. - In contrast, for MDS, in the CONGEST model, we show an $\tildeΩ(n^2)$ lower bound for a constant approximation factor for MDS on $G^2$, whereas an $Ω(n^2)$ lower bound for MDS on $G$ is known only for exact computation. In addition to these highlighted results, we prove a number of other results in the distributed CONGEST model including an $\tildeΩ(n^2)$ lower bound for computing an exact solution to MVC on $G^2$, a conditional hardness result for obtaining a $(1+ε)$-approximation to MVC on $G^2$, and an $O(\log Δ)$-approximation to the MDS problem on $G^2$ in $\mbox{poly}\log n$ rounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Efficient Deterministic Distributed Coloring with Small Bandwidth

We show that the $(degree+1)$-list coloring problem can be solved deterministically in $O(D \cdot \log n \cdot\log^2Δ)$ rounds in the \CONGEST model, where $D$ is the diameter of the graph, $n$ the number of nodes, and $Δ$ the maximum degree. Using the recent polylogarithmic-time deterministic network decomposition algorithm by Rozhoň and Ghaffari [STOC 2020], this implies the first efficient (i.e., $\poly\log n$-time) deterministic \CONGEST algorithm for the $(Δ+1)$-coloring and the $(\mathit{degree}+1)$-list coloring problem. Previously the best known algorithm required $2^{O(\sqrt{\log n})}$ rounds and was not based on network decompositions. Our techniques also lead to deterministic $(\mathit{degree}+1)$-list coloring algorithms for the congested clique and the massively parallel computation (MPC) model. For the congested clique, we obtain an algorithm with time complexity $O(\logΔ\cdot\log\logΔ)$, for the MPC model, we obtain algorithms with round complexity $O(\log^2Δ)$ for the linear-memory regime and $O(\log^2Δ+ \log n)$ for the sublinear memory regime.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Improved Distributed $Δ$-Coloring

We present a randomized distributed algorithm that computes a $Δ$-coloring in any non-complete graph with maximum degree $Δ\geq 4$ in $O(\log Δ) + 2^{O(\sqrt{\log\log n})}$ rounds, as well as a randomized algorithm that computes a $Δ$-coloring in $O((\log \log n)^2)$ rounds when $Δ\in [3, O(1)]$. Both these algorithms improve on an $O(\log^3 n/\log Δ)$-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 $Ω(\log\log n)$ round lower bound of Brandt et al.~[STOC'16].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Local Conflict Coloring Revisited: Linial for Lists

Linial's famous color reduction algorithm reduces a given $m$-coloring of a graph with maximum degree $Δ$ to a $O(Δ^2\log m)$-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their color from a list of allowed colors: given an $m$-coloring in a directed graph of maximum outdegree $β$, if every node has a list of size $Ω(β^2 (\log β+\log\log m + \log \log |\mathcal{C}|))$ from a color space $\mathcal{C}$ then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial's color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local $(deg+1)$-list coloring algorithm from Barenboim et al. [PODC'18] by slightly reducing the runtime to $O(\sqrt{Δ\logΔ})+\log^* n$ and significantly reducing the message size (from huge to roughly $Δ$). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS'16].

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model

We show an $Ω\big(Δ^{\frac{1}{3}-\fracη{3}}\big)$ lower bound on the runtime of any deterministic distributed $\mathcal{O}\big(Δ^{1+η}\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. A node can \textbf{broadcast} a \textbf{single} message of \textbf{unbounded} size to its neighbors and receives the \textbf{set of messages} sent to it by its neighbors. That is, if two neighbors of a node $v\in V$ send the same message to $v$, $v$ will receive this message only a single time; without any further knowledge, $v$ cannot know whether a received message was sent by only one or more than one neighbor. Neighborhood graphs have been essential in the proof of lower bounds for distributed coloring algorithms, e.g., \cite{linial92,Kuhn2006On}. Our proof analyzes the recursive structure of the neighborhood graph of the respective model to devise an $Ω\big(Δ^{\frac{1}{3}-\fracη{3}}\big)$ lower bound on the runtime for any deterministic distributed $\mathcal{O}\big(Δ^{1+η}\big)$-graph coloring algorithm. Furthermore, we hope that the proof technique improves the understanding of neighborhood graphs in general and that it will help towards finding a lower (runtime) bound for distributed graph coloring in the standard \LOCAL\ model. Our proof technique works for one-round algorithms in the standard \LOCAL\ model and provides a simpler and more intuitive proof for an existing $Ω(Δ^2)$ lower bound.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rumor Spreading with Bounded In-Degree

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(Δ/ δ\log n)$, where $Δ$ and $δ$ are the largest and smallest degree of the network.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Wavelet Riesz bases associated to nonisotropic dilations

A bounded, Riemann integrable and measurable set $K\subset \mathbb{R}^d$, which fulfills \[\sum\limits_{γ\inΓ}\mathbb{1}_K(x-γ)=k\text{ almost everywhere, $x\in\mathbb{R}^d$}\] for a lattice $Γ\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. One example of our construction is the first known shearlet Riesz basis.

0 citations0 reviewsNo code linkedOpen access