2 Search Results for "Nakar, Yonatan"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.98
Testing Dynamic Environments: Back to Basics

Authors: Yonatan Nakar and Dana Ron

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We continue the line of work initiated by Goldreich and Ron (Journal of the ACM, 2017) on testing dynamic environments and propose to pursue a systematic study of the complexity of testing basic dynamic environments and local rules. As a first step, in this work we focus on dynamic environments that correspond to elementary cellular automata that evolve according to threshold rules. Our main result is the identification of a set of conditions on local rules, and a meta-algorithm that tests evolution according to local rules that satisfy the conditions. The meta-algorithm has query complexity poly(1/ε), is non-adaptive and has one-sided error. We show that all the threshold rules satisfy the set of conditions, and therefore are poly(1/ε)-testable. We believe that this is a rich area of research and suggest a variety of open problems and natural research directions that may extend and expand our results.
Cite as

Yonatan Nakar and Dana Ron. Testing Dynamic Environments: Back to Basics. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 98:1-98:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nakar_et_al:LIPIcs.ICALP.2021.98,
  author =	{Nakar, Yonatan and Ron, Dana},
  title =	{{Testing Dynamic Environments: Back to Basics}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{98:1--98:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.98},
  URN =		{urn:nbn:de:0030-drops-141672},
  doi =		{10.4230/LIPIcs.ICALP.2021.98},
  annote =	{Keywords: Property Testing}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.53
On the Testability of Graph Partition Properties

Authors: Yonatan Nakar and Dana Ron

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

Abstract
In this work we study the testability of a family of graph partition properties that generalizes a family previously studied by Goldreich, Goldwasser, and Ron (Journal of the ACM, 1998 ). While the family studied by Goldreich, Goldwasser, and Ron includes a variety of natural properties, such as k-colorability and containing a large cut, it does not include other properties of interest, such as split graphs, and more generally (p,q)-colorable graphs. The generalization we consider allows us to impose constraints on the edge-densities within and between parts (relative to the sizes of the parts). We denote the family studied in this work by GPP. We first show that all properties in GPP have a testing algorithm whose query complexity is polynomial in 1/epsilon, where epsilon is the given proximity parameter (and there is no dependence on the size of the graph). As the testing algorithm has two-sided error, we next address the question of which properties in GPP can be tested with one-sided error and query complexity polynomial in 1/epsilon. We answer this question by establishing a characterization result. Namely, we define a subfamily GPP_{0,1} of GPP and show that a property P in GPP is testable by a one-sided error algorithm that has query complexity poly(1/epsilon) if and only if P in GPP_{0,1}.
Cite as

Yonatan Nakar and Dana Ron. On the Testability of Graph Partition Properties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 53:1-53:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{nakar_et_al:LIPIcs.APPROX-RANDOM.2018.53,
  author =	{Nakar, Yonatan and Ron, Dana},
  title =	{{On the Testability of Graph Partition Properties}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.53},
  URN =		{urn:nbn:de:0030-drops-94572},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.53},
  annote =	{Keywords: Graph Partition Properties}
}
  • Refine by Type
  • 2 Document/PDF

  • Refine by Publication Year
  • 1 2021
  • 1 2018

  • Refine by Author
  • 2 Nakar, Yonatan
  • 2 Ron, Dana

  • Refine by Series/Journal
  • 2 LIPIcs

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

  • Refine by Keyword
  • 1 Graph Partition Properties
  • 1 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