5 Search Results for "Ben-Aroya, Avraham"

Document
DOI: 10.4230/LIPIcs.ESA.2023.67
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs

Authors: Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We study the reverse shortest path problem on disk graphs in the plane. In this problem we consider the proximity graph of a set of n disks in the plane of arbitrary radii: In this graph two disks are connected if the distance between them is at most some threshold parameter r. The case of intersection graphs is a special case with r = 0. We give an algorithm that, given a target length k, computes the smallest value of r for which there is a path of length at most k between some given pair of disks in the proximity graph. Our algorithm runs in O^*(n^{5/4}) randomized expected time, which improves to O^*(n^{6/5}) for unit disk graphs, where all the disks have the same radius. Our technique is robust and can be applied to many variants of the problem. One significant variant is the case of weighted proximity graphs, where edges are assigned real weights equal to the distance between the disks or between their centers, and k is replaced by a target weight w. In other variants, we want to optimize a parameter different from r, such as a scale factor of the radii of the disks. The main technique for the decision version of the problem (determining whether the graph with a given r has the desired property) is based on efficient implementations of BFS (for the unweighted case) and of Dijkstra’s algorithm (for the weighted case), using efficient data structures for maintaining the bichromatic closest pair for certain bicliques and several distance functions. The optimization problem is then solved by combining the resulting decision procedure with enhanced variants of the interval shrinking and bifurcation technique of [R. Ben Avraham et al., 2015].
Cite as

Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir. The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.ESA.2023.67,
  author =	{Kaplan, Haim and Katz, Matthew J. and Saban, Rachel and Sharir, Micha},
  title =	{{The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.67},
  URN =		{urn:nbn:de:0030-drops-187208},
  doi =		{10.4230/LIPIcs.ESA.2023.67},
  annote =	{Keywords: Computational geometry, geometric optimization, disk graphs, BFS, Dijkstra’s algorithm, reverse shortest path}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.1
Near-Optimal Erasure List-Decodable Codes

Authors: Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
A code 𝒞 ⊆ {0,1}^n̅ is (s,L) erasure list-decodable if for every word w, after erasing any s symbols of w, the remaining n̅-s symbols have at most L possible completions into a codeword of 𝒞. Non-explicitly, there exist binary ((1-τ)n̅,L) erasure list-decodable codes with rate approaching τ and tiny list-size L = O(log 1/(τ)). Achieving either of these parameters explicitly is a natural open problem (see, e.g., [Guruswami and Indyk, 2002; Guruswami, 2003; Guruswami, 2004]). While partial progress on the problem has been achieved, no prior nontrivial explicit construction achieved rate better than Ω(τ²) or list-size smaller than Ω(1/τ). Furthermore, Guruswami showed no linear code can have list-size smaller than Ω(1/τ) [Guruswami, 2003]. We construct an explicit binary ((1-τ)n̅,L) erasure list-decodable code having rate τ^(1+γ) (for any constant γ > 0 and small τ) and list-size poly(log 1/τ), answering simultaneously both questions, and exhibiting an explicit non-linear code that provably beats the best possible linear code. The binary erasure list-decoding problem is equivalent to the construction of explicit, low-error, strong dispersers outputting one bit with minimal entropy-loss and seed-length. For error ε, no prior explicit construction achieved seed-length better than 2log(1/ε) or entropy-loss smaller than 2log(1/ε), which are the best possible parameters for extractors. We explicitly construct an ε-error one-bit strong disperser with near-optimal seed-length (1+γ)log(1/ε) and entropy-loss O(log log1/ε). The main ingredient in our construction is a new (and almost-optimal) unbalanced two-source extractor. The extractor extracts one bit with constant error from two independent sources, where one source has length n and tiny min-entropy O(log log n) and the other source has length O(log n) and arbitrarily small constant min-entropy rate. When instantiated as a balanced two-source extractor, it improves upon Raz’s extractor [Raz, 2005] in the constant error regime. The construction incorporates recent components and ideas from extractor theory with a delicate and novel analysis needed in order to solve dependency and error issues that prevented previous papers (such as [Li, 2015; Chattopadhyay and Zuckerman, 2019; Cohen, 2016]) from achieving the above results.
Cite as

Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-Optimal Erasure List-Decodable Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 1:1-1:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{benaroya_et_al:LIPIcs.CCC.2020.1,
  author =	{Ben-Aroya, Avraham and Doron, Dean and Ta-Shma, Amnon},
  title =	{{Near-Optimal Erasure List-Decodable Codes}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{1:1--1:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.1},
  URN =		{urn:nbn:de:0030-drops-125531},
  doi =		{10.4230/LIPIcs.CCC.2020.1},
  annote =	{Keywords: Dispersers, Erasure codes, List decoding, Ramsey graphs, Two-source extractors}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.43
Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions

Authors: Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error epsilon for n-bit sources having min-entropy {polylog}(n/epsilon). Unfortunately, the construction’s running-time is {poly}(n/epsilon), which means that with polynomial-time constructions, only polynomially-small errors are possible. Our main result is a {poly}(n,log(1/epsilon))-time computable two-source condenser. For any k >= {polylog}(n/epsilon), our condenser transforms two independent (n,k)-sources to a distribution over m = k-O(log(1/epsilon)) bits that is epsilon-close to having min-entropy m - o(log(1/epsilon)). Hence, achieving entropy gap of o(log(1/epsilon)). The bottleneck for obtaining low error in recent constructions of two-source extractors lies in the use of resilient functions. Informally, this is a function that receives input bits from r players with the property that the function’s output has small bias even if a bounded number of corrupted players feed adversarial inputs after seeing the inputs of the other players. The drawback of using resilient functions is that the error cannot be smaller than ln r/r. This, in return, forces the running time of the construction to be polynomial in 1/epsilon. A key component in our construction is a variant of resilient functions which we call entropy-resilient functions. This variant can be seen as playing the above game for several rounds, each round outputting one bit. The goal of the corrupted players is to reduce, with as high probability as they can, the min-entropy accumulated throughout the rounds. We show that while the bias decreases only polynomially with the number of players in a one-round game, their success probability decreases exponentially in the entropy gap they are attempting to incur in a repeated game.
Cite as

Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{benaroya_et_al:LIPIcs.APPROX-RANDOM.2019.43,
  author =	{Ben-Aroya, Avraham and Cohen, Gil and Doron, Dean and Ta-Shma, Amnon},
  title =	{{Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{43:1--43:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.43},
  URN =		{urn:nbn:de:0030-drops-112587},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.43},
  annote =	{Keywords: Condensers, Extractors, Resilient functions, Explicit constructions}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2018.20
Algorithms for the Discrete Fréchet Distance Under Translation

Authors: Omrit Filtser and Matthew J. Katz

Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)

Abstract
The (discrete) Fréchet distance (DFD) is a popular similarity measure for curves. Often the input curves are not aligned, so one of them must undergo some transformation for the distance computation to be meaningful. Ben Avraham et al. [Rinat Ben Avraham et al., 2015] presented an O(m^3n^2(1+log(n/m))log(m+n))-time algorithm for DFD between two sequences of points of sizes m and n in the plane under translation. In this paper we consider two variants of DFD, both under translation. For DFD with shortcuts in the plane, we present an O(m^2n^2 log^2(m+n))-time algorithm, by presenting a dynamic data structure for reachability queries in the underlying directed graph. In 1D, we show how to avoid the use of parametric search and remove a logarithmic factor from the running time of (the 1D versions of) these algorithms and of an algorithm for the weak discrete Fréchet distance; the resulting running times are thus O(m^2n(1+log(n/m))), for the discrete Fréchet distance, and O(mn log(m+n)), for its two variants. Our 1D algorithms follow a general scheme introduced by Martello et al. [Martello et al., 1984] for the Balanced Optimization Problem (BOP), which is especially useful when an efficient dynamic version of the feasibility decider is available. We present an alternative scheme for BOP, whose advantage is that it yields efficient algorithms quite easily, without having to devise a specially tailored dynamic version of the feasibility decider. We demonstrate our scheme on the most uniform path problem (significantly improving the known bound), and observe that the weak DFD under translation in 1D is a special case of it.
Cite as

Omrit Filtser and Matthew J. Katz. Algorithms for the Discrete Fréchet Distance Under Translation. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{filtser_et_al:LIPIcs.SWAT.2018.20,
  author =	{Filtser, Omrit and Katz, Matthew J.},
  title =	{{Algorithms for the Discrete Fr\'{e}chet Distance Under Translation}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{Eppstein, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.20},
  URN =		{urn:nbn:de:0030-drops-88466},
  doi =		{10.4230/LIPIcs.SWAT.2018.20},
  annote =	{Keywords: curve similarity, discrete Fr\'{e}chet distance, translation, algorithms, BOP}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.3
A New Approach for Constructing Low-Error, Two-Source Extractors

Authors: Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
Our main contribution in this paper is a new reduction from explicit two-source extractors for polynomially-small entropy rate and negligible error to explicit t-non-malleable extractors with seed-length that has a good dependence on t. Our reduction is based on the Chattopadhyay and Zuckerman framework (STOC 2016), and surprisingly we dispense with the use of resilient functions which appeared to be a major ingredient there and in follow-up works. The use of resilient functions posed a fundamental barrier towards achieving negligible error, and our new reduction circumvents this bottleneck. The parameters we require from t-non-malleable extractors for our reduction to work hold in a non-explicit construction, but currently it is not known how to explicitly construct such extractors. As a result we do not give an unconditional construction of an explicit low-error two-source extractor. Nonetheless, we believe our work gives a viable approach for solving the important problem of low-error two-source extractors. Furthermore, our work highlights an existing barrier in constructing low-error two-source extractors, and draws attention to the dependence of the parameter t in the seed-length of the non-malleable extractor. We hope this work would lead to further developments in explicit constructions of both non-malleable and two-source extractors.
Cite as

Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma. A New Approach for Constructing Low-Error, Two-Source Extractors. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benaroya_et_al:LIPIcs.CCC.2018.3,
  author =	{Ben-Aroya, Avraham and Chattopadhyay, Eshan and Doron, Dean and Li, Xin and Ta-Shma, Amnon},
  title =	{{A New Approach for Constructing Low-Error, Two-Source Extractors}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.3},
  URN =		{urn:nbn:de:0030-drops-88877},
  doi =		{10.4230/LIPIcs.CCC.2018.3},
  annote =	{Keywords: Two-Source Extractors, Non-Malleable Extractors, Pseudorandomness, Explicit Constructions}
}
  • Refine by Author
  • 3 Ben-Aroya, Avraham
  • 3 Doron, Dean
  • 3 Ta-Shma, Amnon
  • 2 Katz, Matthew J.
  • 1 Chattopadhyay, Eshan
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Pseudorandomness and derandomization
  • 2 Theory of computation → Computational geometry
  • 1 Theory of computation → Error-correcting codes
  • 1 Theory of computation → Expander graphs and randomness extractors

  • Refine by Keyword
  • 1 BFS
  • 1 BOP
  • 1 Computational geometry
  • 1 Condensers
  • 1 Dijkstra’s algorithm
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2018
  • 1 2019
  • 1 2020
  • 1 2023

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