BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Dominik Kaaser

Dominik Kaaser contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Distributed, Parallel, and Cluster ComputingInformation Theorymath.ITData Structures and AlgorithmsDiscrete MathematicsMachine LearningComputational Geometrymath-phmath.COmath.MPmath.PRSocial and Information Networks

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
9works
0followers
12topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

9 published item(s)

preprint2026arXiv

Fluctuations of the Ising free energy on Erdős-Rényi graphs

We investigate the ferromagnetic Ising model on the Erdős-Rényi random graph $\mathbb{G}(n,m)$ with bounded average degree $d=2m/n$. Specifically, we determine the limiting distribution of $\log Z_{\mathbb{G}(n,m)}(β,B)$, where $Z_{\mathbb{G}(n,m)}(β,B)$ is the partition function at inverse temperature $β>0$ and external field $B\geq0$. If either $B>0$, or $B=0$, $d>1$ and $β>\operatorname{ath}(1/d)$ the limiting distribution is a Gaussian whose variance is of order $Θ(n)$ and is described by a family of stochastic fixed point problems that encode the root magnetisation of two correlated Galton-Watson trees. By contrast, if $B=0$ and either $d\leq1$ or $β<\operatorname{ath}(1/d)$ the limiting distribution is an infinite sum of independent random variables and has bounded variance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed Reconstruction of Noisy Pooled Data

In the pooled data problem we are given a set of $n$ agents, each of which holds a hidden state bit, either $0$ or $1$. A querying procedure returns for a query set the sum of the states of the queried agents. The goal is to reconstruct the states using as few queries as possible. In this paper we consider two noise models for the pooled data problem. In the noisy channel model, the result for each agent flips with a certain probability. In the noisy query model, each query result is subject to random Gaussian noise. Our results are twofold. First, we present and analyze for both error models a simple and efficient distributed algorithm that reconstructs the initial states in a greedy fashion. Our novel analysis pins down the range of error probabilities and distributions for which our algorithm reconstructs the exact initial states with high probability. Secondly, we present simulation results of our algorithm and compare its performance with approximate message passing (AMP) algorithms that are conjectured to be optimal in a number of related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Inference of a Rumor&#39;s Source in the Independent Cascade Model

We consider the so-called Independent Cascade Model for rumor spreading or epidemic processes popularized by Kempe et al.\ [2003]. In this model, a small subset of nodes from a network are the source of a rumor. In discrete time steps, each informed node &#34;infects&#34; each of its uninformed neighbors with probability $p$. While many facets of this process are studied in the literature, less is known about the inference problem: given a number of infected nodes in a network, can we learn the source of the rumor? In the context of epidemiology this problem is often referred to as patient zero problem. It belongs to a broader class of problems where the goal is to infer parameters of the underlying spreading model, see, e.g., Lokhov [NeurIPS&#39;16] or Mastakouri et al. [NeurIPS&#39;20]. In this work we present a maximum likelihood estimator for the rumor&#39;s source, given a snapshot of the process in terms of a set of active nodes $X$ after $t$ steps. Our results show that, for cycle-free graphs, the likelihood estimator undergoes a non-trivial phase transition as a function $t$. We provide a rigorous analysis for two prominent classes of acyclic network, namely $d$-regular trees and Galton-Watson trees, and verify empirically that our heuristics work well in various general networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Hierarchy of Distributed Majority Protocols

We study the Consensus problem among $n$ agents, defined as follows. Initially, each agent holds one of two possible opinions. The goal is to reach a consensus configuration in which every agent shares the same opinion. To this end, agents randomly sample other agents and update their opinion according to a simple update function depending on the sampled opinions. We consider two communication models: the gossip model and a variant of the population model. In the gossip model, agents are activated in parallel, synchronous rounds. In the population model, one agent is activated after the other in a sequence of discrete time steps. For both models we analyze the following natural family of majority processes called $j$-Majority: when activated, every agent samples $j$ other agents uniformly at random (with replacement) and adopts the majority opinion among the sample (breaking ties uniformly at random). As our main result we show a hierarchy among majority protocols: $(j+1)$-Majority (for $j > 1$) converges stochastically faster than $j$-Majority for any initial opinion configuration. In our analysis we use Strassen&#39;s Theorem to prove the existence of a coupling. This gives an affirmative answer for the case of two opinions to an open question asked by Berenbrink et al. [2017].

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Parallel Reconstruction from Pooled Data

In the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal $σ\in \{ 0,1 \}^n$, we can query multiple entries at once and get the total number of non-zero entries in the query as a result. We assume that queries are time-consuming and therefore focus on the setting where all queries are executed in parallel. For the regime where the signal is sparse such that $ || σ||_1 = o(n)$ our results are twofold: First, we propose and analyze a simple and efficient greedy reconstruction algorithm. Secondly, we derive a sharp information-theoretic threshold for the minimum number of queries required to reconstruct $σ$ with high probability. Our first result matches the performance guarantees of much more involved constructions (Karimi et al. 2019). Our second result extends a result of Alaoui et al. (2014) and Scarlett & Cevher (2017) who studied the pooled data problem for dense signals. Finally, our theoretical findings are complemented with empirical simulations. Our data not only confirm the information-theoretic thresholds but also hint at the practical applicability of our pooling scheme and the simple greedy reconstruction algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On Greedily Packing Anchored Rectangles

Consider a set P of points in the unit square U, one of them being the origin. For each point p in P you may draw a rectangle in U with its lower-left corner in p. What is the maximum area such rectangles can cover without overlapping each other? Freedman [1969] posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and Tóth [2011] achieved the first constant coverage of 9.1%; since then, no significant progress was made. While 9.1% might seem low, the authors could not find any instance where their algorithm covers less than 50%, nourishing the hope to eventually prove a 50% bound. While we indeed significantly raise the algorithm&#39;s coverage to 39%, we extinguish the hope of reaching 50% by giving points for which the coverage is below 43.3%. Our analysis studies the algorithm&#39;s average and worst-case density of so-called tiles, which represent the area where a given point can freely choose its maximum-area rectangle. Our approachis comparatively general and may potentially help in analyzing related algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Positive Aging Admits Fast Asynchronous Plurality Consensus

We study distributed plurality consensus among $n$ nodes, each of which initially holds one of $k$ opinions. The goal is to eventually agree on the initially dominant opinion. We consider an asynchronous communication model in which each node is equipped with a random clock. Whenever the clock of a node ticks, it may open communication channels to a constant number of other nodes, chosen uniformly at random or from a list of constantly many addresses acquired in previous steps. The tick rates and the delays for establishing communication channels (channel delays) follow some probability distribution. Once a channel is established, communication between nodes can be performed instantaneously. We consider distributions for the waiting times between ticks and channel delays that have constant mean and the so-called positive aging property. In this setting, asynchronous plurality consensus is fast: if the initial bias between the largest and second largest opinion is at least $\sqrt{n}\log n$, then after $O(\log\log_αk\cdot\log k+\log\log n)$ time all but a $1/ \text{polylog } n$ fraction of nodes have the initial plurality opinion. Here $α$ denotes the initial ratio between the largest and second largest opinion. After additional $O(\log n)$ steps all nodes have the same opinion w.h.p., and this result is tight. If additionally the distributions satisfy a certain density property, which is common in many well-known distributions, we show that consensus is reached in $O(\log \log_αk + \log \log n)$ time for all but $n/\text{polylog } n$ nodes, w.h.p. This implies that for a large range of initial configurations partial consensus can be reached significantly faster in this asynchronous communication model than in the synchronous setting.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simulating Population Protocols in Sub-Constant Time per Interaction

We consider the problem of efficiently simulating population protocols. In the population model, we are given a distributed system of $n$ agents modeled as identical finite-state machines. In each time step, a pair of agents is selected uniformly at random to interact. In an interaction, agents update their states according to a common transition function. We empirically and analytically analyze two classes of simulators for this model. First, we consider sequential simulators executing one interaction after the other. Key to the performance of these simulators is the data structure storing the agents&#39; states. For our analysis, we consider plain arrays, binary search trees, and a novel Dynamic Alias Table data structure. Secondly, we consider batch processing to efficiently update the states of multiple independent agents in one step. For many protocols considered in literature, our simulator requires amortized sub-constant time per interaction and is fast in practice: given a fixed time budget, the implementation of our batched simulator is able to simulate population protocols several orders of magnitude larger compared to the sequential competitors, and can carry out $2^{50}$ interactions among the same number of agents in less than 400s.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Time-space Trade-offs in Population Protocols for the Majority Problem

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of $n$ identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result [Alistarh, Gelashvili, Vojnovic; PODC&#39;15], we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size $n$), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions.

0 citations0 reviewsNo code linkedOpen access