11 Search Results for "Korman, Amos"

Document
DOI: 10.4230/LIPIcs.MFCS.2024.48
Local Certification of Geometric Graph Classes

Authors: Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
The goal of local certification is to locally convince the vertices of a graph G that G satisfies a given property. A prover assigns short certificates to the vertices of the graph, then the vertices are allowed to check their certificates and the certificates of their neighbors, and based only on this local view and their own unique identifier, they must decide whether G satisfies the given property. If the graph indeed satisfies the property, all vertices must accept the instance, and otherwise at least one vertex must reject the instance (for any possible assignment of certificates). The goal is to minimize the size of the certificates. In this paper we study the local certification of geometric and topological graph classes. While it is known that in n-vertex graphs, planarity can be certified locally with certificates of size O(log n), we show that several closely related graph classes require certificates of size Ω(n). This includes penny graphs, unit-distance graphs, (induced) subgraphs of the square grid, 1-planar graphs, and unit-square graphs. These bounds are tight up to a constant factor and give the first known examples of hereditary (and even monotone) graph classes for which the certificates must have linear size. For unit-disk graphs we obtain a lower bound of Ω(n^{1-δ}) for any δ > 0 on the size of the certificates, and an upper bound of O(n log n). The lower bounds are obtained by proving rigidity properties of the considered graphs, which might be of independent interest.
Cite as

Oscar Defrain, Louis Esperet, Aurélie Lagoutte, Pat Morin, and Jean-Florent Raymond. Local Certification of Geometric Graph Classes. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{defrain_et_al:LIPIcs.MFCS.2024.48,
  author =	{Defrain, Oscar and Esperet, Louis and Lagoutte, Aur\'{e}lie and Morin, Pat and Raymond, Jean-Florent},
  title =	{{Local Certification of Geometric Graph Classes}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.48},
  URN =		{urn:nbn:de:0030-drops-206042},
  doi =		{10.4230/LIPIcs.MFCS.2024.48},
  annote =	{Keywords: Local certification, proof labeling schemes, geometric intersection graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.17
Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles

Authors: Surender Baswana and Koustav Bhanja

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Let G be a directed weighted graph on n vertices and m edges with designated source and sink vertices s and t. An edge in G is vital if its removal reduces the capacity of (s,t)-mincut. Since the seminal work of Ford and Fulkerson [CJM 1956], a long line of work has been done on computing the most vital edge and all vital edges of G. However, even after 60 years, the existing results are for either undirected or unweighted graphs. We present the following result for directed weighted graphs that also solves an open problem by Ausiello, Franciosa, Lari, and Ribichini [NETWORKS 2019]. 1. Algorithmic Results: There is an algorithm that computes all vital edges as well as the most vital edge of G using {O}(n) maximum (s,t)-flow computations. Vital edges play a crucial role in the design of sensitivity oracle for (s,t)-mincut - a compact data structure for reporting (s,t)-mincut after insertion/failure of any edge. For directed graphs, the only existing sensitivity oracle is for unweighted graphs by Picard and Queyranne [MPS 1982]. We present the first and optimal sensitivity oracle for directed weighted graphs as follows. 2. Sensitivity Oracles: a) There is an optimal O(n²) space data structure that can report an (s,t)-mincut C in O(|C|) time after the failure/insertion of any edge. b) There is an O(n) space data structure that can report the capacity of (s,t)-mincut after failure or insertion of any edge e in O(1) time if the capacity of edge e is known. A mincut for a vital edge e is an (s,t)-cut of the least capacity in which edge e is outgoing. For unweighted graphs, in a classical work, Picard and Queyranne [MPS 1982] designed an O(m) space directed acyclic graph (DAG) that stores and characterizes all mincuts for all vital edges. Conversely, there is a set containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. We generalize these results for directed weighted graphs as follows. 3. Structural & Combinatorial Results: a) There is a set M containing at most n-1 (s,t)-cuts such that at least one mincut for every vital edge belongs to the set. This bound is tight as well. We also show that set M can be computed using O(n) maximum (s,t)-flow computations. b) We design two compact structures for storing and characterizing all mincuts for all vital edges - (i) an O(m) space DAG for partial and (ii) an O(mn) space structure for complete characterization. To arrive at our results, we develop new techniques, especially a generalization of maxflow-mincut Theorem by Ford and Fulkerson [CJM 1956], which might be of independent interest.
Cite as

Surender Baswana and Koustav Bhanja. Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, & Optimal Sensitivity Oracles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baswana_et_al:LIPIcs.ICALP.2024.17,
  author =	{Baswana, Surender and Bhanja, Koustav},
  title =	{{Vital Edges for (s,t)-Mincut: Efficient Algorithms, Compact Structures, \& Optimal Sensitivity Oracles}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.17},
  URN =		{urn:nbn:de:0030-drops-201601},
  doi =		{10.4230/LIPIcs.ICALP.2024.17},
  annote =	{Keywords: maxflow, vital edges, graph algorithms, structures, st-cuts, sensitivity oracle}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.31
Tight Bounds on Adjacency Labels for Monotone Graph Classes

Authors: Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
A class of graphs admits an adjacency labeling scheme of size b(n), if the vertices in each of its n-vertex graphs can be assigned binary strings (called labels) of length b(n) so that the adjacency of two vertices can be determined solely from their labels. We give bounds on the size of adjacency labels for every family of monotone (i.e., subgraph-closed) classes with a "well-behaved" growth function between 2^Ω(n log n) and 2^O(n^{2-δ}) for any δ > 0. Specifically, we show that for any function f: ℕ → ℝ satisfying log n ⩽ f(n) ⩽ n^{1-δ} for any fixed δ > 0, and some sub-multiplicativity condition, there are monotone graph classes with growth 2^O(nf(n)) that do not admit adjacency labels of size at most f(n) log n. On the other hand, any such class does admit adjacency labels of size O(f(n)log n). Surprisingly this bound is a Θ(log n) factor away from the information-theoretic bound of Ω(f(n)). Our bounds are tight upto constant factors, and the special case when f = log implies that the recently-refuted Implicit Graph Conjecture [Hatami and Hatami, FOCS 2022] also fails within monotone classes. We further show that the Implicit Graph Conjecture holds for all monotone small classes. In other words, any monotone class with growth rate at most n! cⁿ for some constant c > 0, admits adjacency labels of information-theoretic order optimal size. In fact, we show a more general result that is of independent interest: any monotone small class of graphs has bounded degeneracy. We conjecture that the Implicit Graph Conjecture holds for all hereditary small classes.
Cite as

Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ICALP.2024.31,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor and Zhukovskii, Maksim},
  title =	{{Tight Bounds on Adjacency Labels for Monotone Graph Classes}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{31:1--31:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.31},
  URN =		{urn:nbn:de:0030-drops-201741},
  doi =		{10.4230/LIPIcs.ICALP.2024.31},
  annote =	{Keywords: Adjacency labeling, degeneracy, monotone classes, small classes, factorial classes, implicit graph conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.57
Non-Linear Paging

Authors: Ilan Doron-Arad and Joseph (Seffi) Naor

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This model captures the well-studied classic weighted paging and generalized paging problems, and also submodular and supermodular paging, studied here for the first time, that have a range of applications from virtual memory to machine learning. Unlike classic paging, the cache threshold parameter k does not yield good competitive ratios for non-linear paging. Instead, we introduce a novel parameter 𝓁 that generalizes the notion of cache size to the non-linear setting. We obtain a tight deterministic 𝓁-competitive algorithm for general non-linear paging and a o(log²𝓁)-competitive lower bound for randomized algorithms. Our algorithm is based on a new generic LP for the problem that captures both submodular and supermodular paging, in contrast to LPs used for submodular cover settings. We finally focus on the supermodular paging problem, which is a variant of online set cover and online submodular cover, where sets are repeatedly requested to be removed from the cover. We obtain polylogarithmic lower and upper bounds and an offline approximation algorithm.
Cite as

Ilan Doron-Arad and Joseph (Seffi) Naor. Non-Linear Paging. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 57:1-57:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{doronarad_et_al:LIPIcs.ICALP.2024.57,
  author =	{Doron-Arad, Ilan and Naor, Joseph (Seffi)},
  title =	{{Non-Linear Paging}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{57:1--57:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.57},
  URN =		{urn:nbn:de:0030-drops-202000},
  doi =		{10.4230/LIPIcs.ICALP.2024.57},
  annote =	{Keywords: paging, competitive analysis, non-linear paging, submodular and supermodular functions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.120
Caching Connections in Matchings

Authors: Yaniv Sadeh and Haim Kaplan

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Motivated by the desire to utilize a limited number of configurable optical switches by recent advances in Software Defined Networks (SDNs), we define an online problem which we call the Caching in Matchings problem. This problem has a natural combinatorial structure and therefore may find additional applications in theory and practice. In the Caching in Matchings problem our cache consists of k matchings of connections between servers that form a bipartite graph. To cache a connection we insert it into one of the k matchings possibly evicting at most two other connections from this matching. This problem resembles the problem known as Connection Caching [Cohen et al., 2000], where we also cache connections but our only restriction is that they form a graph with bounded degree k. Our results show a somewhat surprising qualitative separation between the problems: The competitive ratio of any online algorithm for caching in matchings must depend on the size of the graph. Specifically, we give a deterministic O(nk) competitive and randomized O(n log k) competitive algorithms for caching in matchings, where n is the number of servers and k is the number of matchings. We also show that the competitive ratio of any deterministic algorithm is Ω(max(n/k,k)) and of any randomized algorithm is Ω(log (n/(k² log k)) ⋅ log k). In particular, the lower bound for randomized algorithms is Ω(log n) regardless of k, and can be as high as Ω(log² n) if k = n^{1/3}, for example. We also show that if we allow the algorithm to use at least 2k-1 matchings compared to k used by the optimum then we match the competitive ratios of connection catching which are independent of n. Interestingly, we also show that even a single extra matching for the algorithm allows to get substantially better bounds.
Cite as

Yaniv Sadeh and Haim Kaplan. Caching Connections in Matchings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sadeh_et_al:LIPIcs.ICALP.2024.120,
  author =	{Sadeh, Yaniv and Kaplan, Haim},
  title =	{{Caching Connections in Matchings}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{120:1--120:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.120},
  URN =		{urn:nbn:de:0030-drops-202639},
  doi =		{10.4230/LIPIcs.ICALP.2024.120},
  annote =	{Keywords: Caching, Matchings, Caching in Matchings, Edge Coloring, Online Algorithms}
}
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}
}
  • Refine by Author
  • 6 Korman, Amos
  • 3 Rodeh, Yoav
  • 2 Boczkowski, Lucas
  • 1 Baswana, Surender
  • 1 Bhanja, Koustav
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Graph theory
  • 1 Applied computing → Computational biology
  • 1 Computing methodologies → Distributed computing methodologies
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 1 Adjacency labeling
  • 1 Algorithmic Mechanism Design
  • 1 Ant recruitment
  • 1 Average Case Analysis
  • 1 CCRW
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 5 2024
  • 2 2018
  • 1 2011
  • 1 2017
  • 1 2019
  • Show More...

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