12 Search Results for "Ben-Aroya, Avraham"

Volume

OASIcs, Volume 125

35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

DX 2024, November 4-7, 2024, Vienna, Austria

Editors: Ingo Pill, Avraham Natan, and Franz Wotawa

Document
DOI: 10.4230/OASIcs.DX.2024.2
A Model-Based Approach for Monitoring and Diagnosing Digital Twin Discrepancies

Authors: Elaheh Hosseinkhani, Martin Leucker, Martin Sachenbacher, Hendrik Streichhahn, and Lars B. Vosteen

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
Recent decades have seen the increasing use of Digital Twins (DTs) - that is, digital models used over the lifetime of a physical product or system for tasks such as predictive maintenance or optimization - in a number of domains such as buildings, manufacturing, or design. DTs face a challenge known as the DT synchronization problem; a DT, often based on machine-learned, or complex simulation models, needs to adequately mirror the physical product or system at all times, as any deviations might affect the quality of predictions or control actions. In this paper, we present a model-based approach that aims to add a level of awareness to DT models by supervising if they are in sync with the physical counterpart. The approach is agnostic to the type of models used in the DT, as long as they are compositional, and based on monitoring critical properties (behavioral or functional aspects) of the system at run-time. In the case violations are detected, it reasons on the DT’s structure to localize and identify parts of the model that cause deviations and need to be adapted. We give a formal description and an implementation of this approach, and illustrate it with an example from building climatisation.
Cite as

Elaheh Hosseinkhani, Martin Leucker, Martin Sachenbacher, Hendrik Streichhahn, and Lars B. Vosteen. A Model-Based Approach for Monitoring and Diagnosing Digital Twin Discrepancies. In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hosseinkhani_et_al:OASIcs.DX.2024.2,
  author =	{Hosseinkhani, Elaheh and Leucker, Martin and Sachenbacher, Martin and Streichhahn, Hendrik and Vosteen, Lars B.},
  title =	{{A Model-Based Approach for Monitoring and Diagnosing Digital Twin Discrepancies}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{2:1--2:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.2},
  URN =		{urn:nbn:de:0030-drops-220944},
  doi =		{10.4230/OASIcs.DX.2024.2},
  annote =	{Keywords: Digital Twins, Runtime Verification, Diagnosis, FDIR, TeSSLa}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.DX.2024
OASIcs, Volume 125, DX 2024, Complete Volume

Authors: Ingo Pill, Avraham Natan, and Franz Wotawa

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
OASIcs, Volume 125, DX 2024, Complete Volume
Cite as

35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 1-534, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Proceedings{pill_et_al:OASIcs.DX.2024,
  title =	{{OASIcs, Volume 125, DX 2024, Complete Volume}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{1--534},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024},
  URN =		{urn:nbn:de:0030-drops-222256},
  doi =		{10.4230/OASIcs.DX.2024},
  annote =	{Keywords: OASIcs, Volume 125, DX 2024, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/OASIcs.DX.2024.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Ingo Pill, Avraham Natan, and Franz Wotawa

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pill_et_al:OASIcs.DX.2024.0,
  author =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{0:i--0:xvi},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.0},
  URN =		{urn:nbn:de:0030-drops-222242},
  doi =		{10.4230/OASIcs.DX.2024.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/OASIcs.DX.2024.8
Diagnosing Multi-Agent STRIPS Plans

Authors: Avraham Natan, Roni Stern, Meir Kalech, William Yeoh, and Tran Cao Son

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
The increasing use of multi-agent systems demands that many challenges be addressed. One such challenge is diagnosing failed multi-agent plan executions, sometimes in system setups where the different agents are not willing to disclose their private actions. One formalism for generating multi-agent plans is the well-known MA-STRIPS formalism. While there have been approaches for delivering as robust plans as possible, we focus on the plan execution stage. Specifically, we address the problem of diagnosing plans that failed their execution. We propose a Model-Based Diagnosis approach to solve this problem. Given an MA-STRIPS problem, a plan that solves it, and an observation that indicates execution failure, we define the MA-STRIPS diagnosis problem. We compile that problem into a boolean satisfiability problem (SAT) and then use an off-the-shelf SAT solver to obtain candidate diagnoses. We further expand this approach to address privacy by proposing a distributed algorithm that can find these same diagnoses in a decentralized manner. Additionally, we propose an enhancement to the distributed algorithm that uses information generated during the diagnosis process to provide significant speedups. We found that the improved algorithm runs more than 10 times faster than the basic decentralized version and, in one case, runs faster than the centralized algorithm.
Cite as

Avraham Natan, Roni Stern, Meir Kalech, William Yeoh, and Tran Cao Son. Diagnosing Multi-Agent STRIPS Plans. In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{natan_et_al:OASIcs.DX.2024.8,
  author =	{Natan, Avraham and Stern, Roni and Kalech, Meir and Yeoh, William and Son, Tran Cao},
  title =	{{Diagnosing Multi-Agent STRIPS Plans}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{8:1--8:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.8},
  URN =		{urn:nbn:de:0030-drops-221001},
  doi =		{10.4230/OASIcs.DX.2024.8},
  annote =	{Keywords: Model-based diagnosis, Multi-agent systems, Distributed diagnosis, Privacy}
}
Document
DOI: 10.4230/OASIcs.DX.2024.17
Real-Time Sensor Fault Detection in Drones: A Correlation-Based Algorithmic Approach

Authors: Inbal Roshanski, Magenya Roshanski, and Meir Kalech

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
Drones, or unmanned aerial vehicles (UAVs), are becoming increasingly vital across various industries, where their reliable operation is crucial for safety and efficiency. Ensuring this reliability requires the early detection of sensor-related faults, which are critical for maintaining the performance and safety of UAVs. This study addresses this challenge by leveraging real-world data from an Aero-Sentinel Military UAV Sentinel G2 quadcopter. The data was collected through a collaboration with Maris-Tech Ltd, using their advanced Mercury Nano system to capture detailed communication between the drone and its control unit. A set of correlation-based algorithms was developed and evaluated, specifically tailored to address the unique complexities of drone sensor data, which is often influenced by environmental factors. Among the algorithms tested, two novel methods emerged as particularly effective, demonstrating significant improvement compared to previous methods, in fault detection accuracy. These methods, designed to accurately identify and predict sensor malfunctions, offer a robust solution for enhancing the reliability and safety of UAV operations.
Cite as

Inbal Roshanski, Magenya Roshanski, and Meir Kalech. Real-Time Sensor Fault Detection in Drones: A Correlation-Based Algorithmic Approach. In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{roshanski_et_al:OASIcs.DX.2024.17,
  author =	{Roshanski, Inbal and Roshanski, Magenya and Kalech, Meir},
  title =	{{Real-Time Sensor Fault Detection in Drones: A Correlation-Based Algorithmic Approach}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{17:1--17:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.17},
  URN =		{urn:nbn:de:0030-drops-221092},
  doi =		{10.4230/OASIcs.DX.2024.17},
  annote =	{Keywords: Drones, Sensor Fault Detection, Correlation-Based Algorithms, Sensor Data Analysis, Anomaly Detection, Data-Driven Fault Detection}
}
Document
Short Paper
DOI: 10.4230/OASIcs.DX.2024.23
Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions (Short Paper)

Authors: Avraham Natan, Roni Stern, and Meir Kalech

Published in: OASIcs, Volume 125, 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)

Abstract
Reinforcement learning (RL) algorithms output policies specifying which action an agent should take in a given state. However, faults can sometimes arise during policy execution due to internal faults in the agent. As a result, actions may have unexpected effects. In this work, we aim to diagnose such faults and infer their root cause. We consider two types of diagnosis problems. In the first, which we call RLDXw, we assume we only know what a normal execution looks like. In the second, called RLDXs, we assume we have models for the faulty behavior of a component, which we call fault modes. The solution to RLDXw is a time step at which a fault occurred for the first time. The solution to RLDXs is more informative, represented as a fault mode according to which the RL task was executed. Solving those problems is useful in practice to facilitate efficient repair of faulty agents, since it can focus the repair efforts on specific actions. We formally define RLDXw and RLDXs and design two algorithms called WFMa and SFMa for solving them. We evaluate our algorithms on a benchmark of RL domains and discuss their strengths and limitations. When the number of the observed states increases, both WFMa and SFMa report a decrease in runtime (up to significantly 6.5 times faster). Additionally, the runtime of SFMa increases linearly with the increase in candidate fault modes.
Cite as

Avraham Natan, Roni Stern, and Meir Kalech. Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions (Short Paper). In 35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024). Open Access Series in Informatics (OASIcs), Volume 125, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{natan_et_al:OASIcs.DX.2024.23,
  author =	{Natan, Avraham and Stern, Roni and Kalech, Meir},
  title =	{{Diagnosing Non-Intermittent Anomalies in Reinforcement Learning Policy Executions}},
  booktitle =	{35th International Conference on Principles of Diagnosis and Resilient Systems (DX 2024)},
  pages =	{23:1--23:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-356-0},
  ISSN =	{2190-6807},
  year =	{2024},
  volume =	{125},
  editor =	{Pill, Ingo and Natan, Avraham and Wotawa, Franz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.DX.2024.23},
  URN =		{urn:nbn:de:0030-drops-221151},
  doi =		{10.4230/OASIcs.DX.2024.23},
  annote =	{Keywords: Diagnosis, Reinforcement Learning, Autonomous Systems}
}
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.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.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.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.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.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
  • 4 Natan, Avraham
  • 3 Ben-Aroya, Avraham
  • 3 Doron, Dean
  • 3 Kalech, Meir
  • 3 Ta-Shma, Amnon
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Diagnosis
  • 1 Anomaly Detection
  • 1 Autonomous Systems
  • 1 BFS
  • 1 BOP
  • Show More...

  • Refine by Type
  • 11 document
  • 1 volume

  • Refine by Publication Year
  • 7 2024
  • 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 About DROPS Imprint Privacy Contact