3 results
Now showing1 - 3 of 3
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Information-theoretic and algorithmic aspects of parallel and distributed reconstruction from pooled dataIn the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. ...Publicationtype: Journal Article57 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , On the hierarchy of distributed majority protocols(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2022-12); ; ; ; 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’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. [PODC 2017].Publicationtype: Conference PaperScopus© Citations 1 48 67 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , On the parallel reconstruction from pooled dataIn the pooled data problem the goal is to efficiently reconstruct a binary signal from additive measurements. Given a signal sigmain 0, 1n, 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 VertsigmaVert₁= 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 s 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.Publicationtype: Conference Paper25