Search Results

Documents authored by Korman, Amos

Document
DOI: 10.4230/LIPIcs.STACS.2020.28
Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths

Authors: Brieuc Guinard and Amos Korman

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
Search patterns of randomly oriented steps of different lengths have been observed on all scales of the biological world, ranging from microscopic to the ecological, including in protein motors, bacteria, T-cells, honeybees, marine predators, and more, see e.g., [Humphries et al., 2010; Jansen et al., 2012; Reynolds et al., 2017; Schuster and Levandowsky, 1996; Humphries et al., 2010; Viswanathan et al., 1996; Viswanathan et al., 1999]. Through different models, it has been demonstrated that adopting a variety in the magnitude of the step lengths can greatly improve the search efficiency. However, the precise connection between the search efficiency and the number of step lengths in the repertoire of the searcher has not been identified. Motivated by biological examples in one-dimensional terrains, a recent paper studied the best cover time on an n-node cycle that can be achieved by a random walk process that uses k step lengths [Boczkowski et al., 2018]. By tuning the lengths and corresponding probabilities the authors therein showed that the best cover time is roughly n^{1+Θ(1/k)}. While this bound is useful for large values of k, it is hardly informative for small k values, which are of interest in biology [Auger-Méthé et al., 2015; Bénichou et al., 2011; Lomholt et al., 2008; {Reynolds}, 2014]. In this paper, we provide a tight bound for the cover time of such a walk, for every integer k> 1. Specifically, up to lower order polylogarithmic factors, the cover time is n^{1+1/(2k-1)}. For k=2,3, 4 and 5 the bound is thus n^{4/3}, n^{6/5}, n^{8/7}, and n^{10/9}, respectively. Informally, our result implies that, as long as the number of step lengths k is not too large, incorporating an additional step length to the repertoire of the process enables to improve the cover time by a polynomial factor, but the extent of the improvement gradually decreases with k.
Cite as

Brieuc Guinard and Amos Korman. Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 28:1-28:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guinard_et_al:LIPIcs.STACS.2020.28,
  author =	{Guinard, Brieuc and Korman, Amos},
  title =	{{Tight Bounds for the Cover Times of Random Walks with Heterogeneous Step Lengths}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{28:1--28:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.28},
  URN =		{urn:nbn:de:0030-drops-118892},
  doi =		{10.4230/LIPIcs.STACS.2020.28},
  annote =	{Keywords: Computational Biology, Randomness in Computing, Search Algorithms, Random Walks, L\'{e}vy Flights, Intermittent Search, CCRW}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.146
Multi-Round Cooperative Search Games with Multiple Players

Authors: Amos Korman and Yoav Rodeh

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Assume that a treasure is placed in one of M boxes according to a known distribution and that k searchers are searching for it in parallel during T rounds. We study the question of how to incentivize selfish players so that group performance would be maximized. Here, this is measured by the success probability, namely, the probability that at least one player finds the treasure. We focus on congestion policies C(l) that specify the reward that a player receives if it is one of l players that (simultaneously) find the treasure for the first time. Our main technical contribution is proving that the exclusive policy, in which C(1)=1 and C(l)=0 for l>1, yields a price of anarchy of (1-(1-{1}/{k})^{k})^{-1}, and that this is the best possible price among all symmetric reward mechanisms. For this policy we also have an explicit description of a symmetric equilibrium, which is in some sense unique, and moreover enjoys the best success probability among all symmetric profiles. For general congestion policies, we show how to polynomially find, for any theta>0, a symmetric multiplicative (1+theta)(1+C(k))-equilibrium. Together with an appropriate reward policy, a central entity can suggest players to play a particular profile at equilibrium. As our main conceptual contribution, we advocate the use of symmetric equilibria for such purposes. Besides being fair, we argue that symmetric equilibria can also become highly robust to crashes of players. Indeed, in many cases, despite the fact that some small fraction of players crash (or refuse to participate), symmetric equilibria remain efficient in terms of their group performances and, at the same time, serve as approximate equilibria. We show that this principle holds for a class of games, which we call monotonously scalable games. This applies in particular to our search game, assuming the natural sharing policy, in which C(l)=1/l. For the exclusive policy, this general result does not hold, but we show that the symmetric equilibrium is nevertheless robust under mild assumptions.
Cite as

Amos Korman and Yoav Rodeh. Multi-Round Cooperative Search Games with Multiple Players. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 146:1-146:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{korman_et_al:LIPIcs.ICALP.2019.146,
  author =	{Korman, Amos and Rodeh, Yoav},
  title =	{{Multi-Round Cooperative Search Games with Multiple Players}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{146:1--146:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.146},
  URN =		{urn:nbn:de:0030-drops-107227},
  doi =		{10.4230/LIPIcs.ICALP.2019.146},
  annote =	{Keywords: Algorithmic Mechanism Design, Parallel Algorithms, Collaborative Search, Fault-Tolerance, Price of Anarchy, Price of Stability, Symmetric Equilibria}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.54
Searching a Tree with Permanently Noisy Advice

Authors: Lucas Boczkowski, Amos Korman, and Yoav Rodeh

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We consider a search problem on trees using unreliable guiding instructions. Specifically, an agent starts a search at the root of a tree aiming to find a treasure hidden at one of the nodes by an adversary. Each visited node holds information, called advice, regarding the most promising neighbor to continue the search. However, the memory holding this information may be unreliable. Modeling this scenario, we focus on a probabilistic setting. That is, the advice at a node is a pointer to one of its neighbors. With probability q each node is faulty, independently of other nodes, in which case its advice points at an arbitrary neighbor, chosen uniformly at random. Otherwise, the node is sound and points at the correct neighbor. Crucially, the advice is permanent, in the sense that querying a node several times would yield the same answer. We evaluate efficiency by two measures: The move complexity denotes the expected number of edge traversals, and the query complexity denotes the expected number of queries. Let Delta denote the maximal degree. Roughly speaking, the main message of this paper is that a phase transition occurs when the noise parameter q is roughly 1/sqrt{Delta}. More precisely, we prove that above the threshold, every search algorithm has query complexity (and move complexity) which is both exponential in the depth d of the treasure and polynomial in the number of nodes n. Conversely, below the threshold, there exists an algorithm with move complexity O(d sqrt{Delta}), and an algorithm with query complexity O(sqrt{Delta}log Delta log^2 n). Moreover, for the case of regular trees, we obtain an algorithm with query complexity O(sqrt{Delta}log n log log n). For q that is below but close to the threshold, the bound for the move complexity is tight, and the bounds for the query complexity are not far from the lower bound of Omega(sqrt{Delta}log_Delta n). In addition, we also consider a semi-adversarial variant, in which an adversary chooses the direction of advice at faulty nodes. For this variant, the threshold for efficient moving algorithms happens when the noise parameter is roughly 1/Delta. Above this threshold a simple protocol that follows each advice with a fixed probability already achieves optimal move complexity.
Cite as

Lucas Boczkowski, Amos Korman, and Yoav Rodeh. Searching a Tree with Permanently Noisy Advice. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boczkowski_et_al:LIPIcs.ESA.2018.54,
  author =	{Boczkowski, Lucas and Korman, Amos and Rodeh, Yoav},
  title =	{{Searching a Tree with Permanently Noisy Advice}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.54},
  URN =		{urn:nbn:de:0030-drops-95176},
  doi =		{10.4230/LIPIcs.ESA.2018.54},
  annote =	{Keywords: Data structures, Graph search, Average Case Analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.49
Limits for Rumor Spreading in Stochastic Populations

Authors: Lucas Boczkowski, Ofer Feinerman, Amos Korman, and Emanuele Natale

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
Biological systems can share and collectively process information to yield emergent effects, despite inherent noise in communication. While man-made systems often employ intricate structural solutions to overcome noise, the structure of many biological systems is more amorphous. It is not well understood how communication noise may affect the computational repertoire of such groups. To approach this question we consider the basic collective task of rumor spreading, in which information from few knowledgeable sources must reliably flow into the rest of the population. In order to study the effect of communication noise on the ability of groups that lack stable structures to efficiently solve this task, we consider a noisy version of the uniform PULL model. We prove a lower bound which implies that, in the presence of even moderate levels of noise that affect all facets of the communication, no scheme can significantly outperform the trivial one in which agents have to wait until directly interacting with the sources. Our results thus show an exponential separation between the uniform PUSH and PULL communication models in the presence of noise. Such separation may be interpreted as suggesting that, in order to achieve efficient rumor spreading, a system must exhibit either some degree of structural stability or, alternatively, some facet of the communication which is immune to noise. We corroborate our theoretical findings with a new analysis of experimental data regarding recruitment in Cataglyphis Niger desert ants.
Cite as

Lucas Boczkowski, Ofer Feinerman, Amos Korman, and Emanuele Natale. Limits for Rumor Spreading in Stochastic Populations. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boczkowski_et_al:LIPIcs.ITCS.2018.49,
  author =	{Boczkowski, Lucas and Feinerman, Ofer and Korman, Amos and Natale, Emanuele},
  title =	{{Limits for Rumor Spreading in Stochastic Populations}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{49:1--49:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.49},
  URN =		{urn:nbn:de:0030-drops-83207},
  doi =		{10.4230/LIPIcs.ITCS.2018.49},
  annote =	{Keywords: Noisy communication, Passive communication, Ant recruitment, Hypothesis testing}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.81
The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

Authors: Amos Korman and Yoav Rodeh

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We introduce the dependent doors problem as an abstraction for situations in which one must perform a sequence of possibly dependent decisions, without receiving feedback information on the effectiveness of previously made actions. Informally, the problem considers a set of d doors that are initially closed, and the aim is to open all of them as fast as possible. To open a door, the algorithm knocks on it and it might open or not according to some probability distribution. This distribution may depend on which other doors are currently open, as well as on which other doors were open during each of the previous knocks on that door. The algorithm aims to minimize the expected time until all doors open. Crucially, it must act at any time without knowing whether or which other doors have already opened. In this work, we focus on scenarios where dependencies between doors are both positively correlated and acyclic. The fundamental distribution of a door describes the probability it opens in the best of conditions (with respect to other doors being open or closed). We show that if in two configurations of d doors corresponding doors share the same fundamental distribution, then these configurations have the same optimal running time up to a universal constant, no matter what are the dependencies between doors and what are the distributions. We also identify algorithms that are optimal up to a universal constant factor. For the case in which all doors share the same fundamental distribution we additionally provide a simpler algorithm, and a formula to calculate its running time. We furthermore analyse the price of lacking feedback for several configurations governed by standard fundamental distributions. In particular, we show that the price is logarithmic in d for memoryless doors, but can potentially grow to be linear in d for other distributions. We then turn our attention to investigate precise bounds. Even for the case of two doors, identifying the optimal sequence is an intriguing combinatorial question. Here, we study the case of two cascading memoryless doors. That is, the first door opens on each knock independently with probability p_1. The second door can only open if the first door is open, in which case it will open on each knock independently with probability p_2. We solve this problem almost completely by identifying algorithms that are optimal up to an additive term of 1.
Cite as

Amos Korman and Yoav Rodeh. The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{korman_et_al:LIPIcs.ICALP.2017.81,
  author =	{Korman, Amos and Rodeh, Yoav},
  title =	{{The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{81:1--81:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.81},
  URN =		{urn:nbn:de:0030-drops-73738},
  doi =		{10.4230/LIPIcs.ICALP.2017.81},
  annote =	{Keywords: No Feedback, Sequential Decisions, Probabilistic Environment, Exploration and Exploitation, Golden Ratio}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.69
Tight Bounds For Distributed MST Verification

Authors: Liah Kor, Amos Korman, and David Peleg

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
This paper establishes tight bounds for the Minimum-weight Spanning Tree (MST) verification problem in the distributed setting. Specifically, we provide an MST verification algorithm that achieves simultaneously tilde ~O(|E|) messages and $tilde O(sqrt{n} + D) time, where |E| is the number of edges in the given graph G and D is G's diameter. On the negative side, we show that any MST verification algorithm must send Omega(|E|) messages and incur ~Omega(sqrt{n} + D) time in worst case. Our upper bound result appears to indicate that the verification of an MST may be easier than its construction, since for MST construction, both lower bounds of Omega(|E|) messages and Omega(sqrt{n} + D) time hold, but at the moment there is no known distributed algorithm that constructs an MST and achieves simultaneously tilde O(|E|) messages and ´~O(sqrt{n} + D) time. Specifically, the best known time-optimal algorithm (using ~O(sqrt{n} + D) time) requires O(|E|+n^{3/2}) messages, and the best known message-optimal algorithm (using ~O(|E|) messages) requires O(n) time. On the other hand, our lower bound results indicate that the verification of an MST is not significantly easier than its construction.
Cite as

Liah Kor, Amos Korman, and David Peleg. Tight Bounds For Distributed MST Verification. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 69-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kor_et_al:LIPIcs.STACS.2011.69,
  author =	{Kor, Liah and Korman, Amos and Peleg, David},
  title =	{{Tight Bounds For Distributed MST Verification}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{69--80},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.69},
  URN =		{urn:nbn:de:0030-drops-30000},
  doi =		{10.4230/LIPIcs.STACS.2011.69},
  annote =	{Keywords: distributed algorithms, distributed verification, labeling schemes, minimum-weight spanning tree}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact