2 Search Results for "Cohen Sidon, Omer"

Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2025.2
Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk)

Authors: Dana Ron

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
This short paper accompanies an invited talk given at ICALP2025. It is an informal, high-level presentation of tolerant testing and distance approximation. It includes some general results as well as a few specific ones, with the aim of providing a taste of this research direction within the area of sublinear algorithms.
Cite as

Dana Ron. Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk). In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ron:LIPIcs.ICALP.2025.2,
  author =	{Ron, Dana},
  title =	{{Let’s Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{2:1--2:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.2},
  URN =		{urn:nbn:de:0030-drops-233798},
  doi =		{10.4230/LIPIcs.ICALP.2025.2},
  annote =	{Keywords: Sublinear Algorithms, Tolerant Property Testing, Distance Approximation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.44
Sample-Based Distance-Approximation for Subsequence-Freeness

Authors: Omer Cohen Sidon and Dana Ron

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this work, we study the problem of approximating the distance to subsequence-freeness in the sample-based distribution-free model. For a given subsequence (word) w = w_1 … w_k, a sequence (text) T = t_1 … t_n is said to contain w if there exist indices 1 ≤ i_1 < … < i_k ≤ n such that t_{i_{j}} = w_j for every 1 ≤ j ≤ k. Otherwise, T is w-free. Ron and Rosin (ACM TOCT 2022) showed that the number of samples both necessary and sufficient for one-sided error testing of subsequence-freeness in the sample-based distribution-free model is Θ(k/ε). Denoting by Δ(T,w,p) the distance of T to w-freeness under a distribution p:[n] → [0,1], we are interested in obtaining an estimate Δ̂, such that |Δ̂ - Δ(T,w,p)| ≤ δ with probability at least 2/3, for a given distance parameter δ. Our main result is an algorithm whose sample complexity is Õ(k²/δ²). We first present an algorithm that works when the underlying distribution p is uniform, and then show how it can be modified to work for any (unknown) distribution p. We also show that a quadratic dependence on 1/δ is necessary.
Cite as

Omer Cohen Sidon and Dana Ron. Sample-Based Distance-Approximation for Subsequence-Freeness. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cohensidon_et_al:LIPIcs.ICALP.2023.44,
  author =	{Cohen Sidon, Omer and Ron, Dana},
  title =	{{Sample-Based Distance-Approximation for Subsequence-Freeness}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.44},
  URN =		{urn:nbn:de:0030-drops-180964},
  doi =		{10.4230/LIPIcs.ICALP.2023.44},
  annote =	{Keywords: Property Testing, Distance Approximation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023

  • Refine by Author
  • 2 Ron, Dana
  • 1 Cohen Sidon, Omer

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms

  • Refine by Keyword
  • 2 Distance Approximation
  • 1 Property Testing
  • 1 Sublinear Algorithms
  • 1 Tolerant Property Testing

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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