3 Search Results for "Haddad-Zaknoon, Catherine A."


Document
Track B: Automata, Logic, Semantics, and Theory of Programming
On the Length of Strongly Monotone Descending Chains over ℕ^d

Authors: Sylvain Schmitz and Lia Schütze

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


Abstract
A recent breakthrough by Künnemann, Mazowiecki, Schütze, Sinclair-Banks, and Węgrzycki (ICALP 2023) bounds the running time for the coverability problem in d-dimensional vector addition systems under unary encoding to n^{2^{O(d)}}, improving on Rackoff’s n^{2^{O(dlg d)}} upper bound (Theor. Comput. Sci. 1978), and provides conditional matching lower bounds. In this paper, we revisit Lazić and Schmitz' "ideal view" of the backward coverability algorithm (Inform. Comput. 2021) in the light of this breakthrough. We show that the controlled strongly monotone descending chains of downwards-closed sets over ℕ^d that arise from the dual backward coverability algorithm of Lazić and Schmitz on d-dimensional unary vector addition systems also enjoy this tight n^{2^{O(d)}} upper bound on their length, and that this also translates into the same bound on the running time of the backward coverability algorithm. Furthermore, our analysis takes place in a more general setting than that of Lazić and Schmitz, which allows to show the same results and improve on the 2EXPSPACE upper bound derived by Benedikt, Duff, Sharad, and Worrell (LICS 2017) for the coverability problem in invertible affine nets.

Cite as

Sylvain Schmitz and Lia Schütze. On the Length of Strongly Monotone Descending Chains over ℕ^d. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 153:1-153:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{schmitz_et_al:LIPIcs.ICALP.2024.153,
  author =	{Schmitz, Sylvain and Sch\"{u}tze, Lia},
  title =	{{On the Length of Strongly Monotone Descending Chains over \mathbb{N}^d}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{153:1--153: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.153},
  URN =		{urn:nbn:de:0030-drops-202964},
  doi =		{10.4230/LIPIcs.ICALP.2024.153},
  annote =	{Keywords: Vector addition system, coverability, well-quasi-order, order ideal, affine net}
}
Document
On Testing Decision Tree

Authors: Nader H. Bshouty and Catherine A. Haddad-Zaknoon

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
In this paper, we study testing decision tree of size and depth that are significantly smaller than the number of attributes n. Our main result addresses the problem of poly(n,1/ε) time algorithms with poly(s,1/ε) query complexity (independent of n) that distinguish between functions that are decision trees of size s from functions that are ε-far from any decision tree of size ϕ(s,1/ε), for some function ϕ > s. The best known result is the recent one that follows from Blanc, Lange and Tan, [Guy Blanc et al., 2020], that gives ϕ(s,1/ε) = 2^{O((log³s)/ε³)}. In this paper, we give a new algorithm that achieves ϕ(s,1/ε) = 2^{O(log² (s/ε))}. Moreover, we study the testability of depth-d decision tree and give a distribution free tester that distinguishes between depth-d decision tree and functions that are ε-far from depth-d² decision tree.

Cite as

Nader H. Bshouty and Catherine A. Haddad-Zaknoon. On Testing Decision Tree. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.STACS.2022.17,
  author =	{Bshouty, Nader H. and Haddad-Zaknoon, Catherine A.},
  title =	{{On Testing Decision Tree}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.17},
  URN =		{urn:nbn:de:0030-drops-158273},
  doi =		{10.4230/LIPIcs.STACS.2022.17},
  annote =	{Keywords: Testing decision trees}
}
Document
Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives

Authors: Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, and Yara Zaknoon

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)


Abstract
We study the problem of determining the exact number of defective items in an adaptive group testing by using a minimum number of tests. We improve the existing algorithm and prove a lower bound that shows that the number of tests in our algorithm is optimal up to small additive terms.

Cite as

Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos, Foad Moalem, Jalal Nada, Elias Noufi, and Yara Zaknoon. Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.SWAT.2020.18,
  author =	{Bshouty, Nader H. and Haddad-Zaknoon, Catherine A. and Boulos, Raghd and Moalem, Foad and Nada, Jalal and Noufi, Elias and Zaknoon, Yara},
  title =	{{Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.18},
  URN =		{urn:nbn:de:0030-drops-122658},
  doi =		{10.4230/LIPIcs.SWAT.2020.18},
  annote =	{Keywords: Group Testing, Randomized Algorithm}
}
  • Refine by Author
  • 2 Bshouty, Nader H.
  • 2 Haddad-Zaknoon, Catherine A.
  • 1 Boulos, Raghd
  • 1 Moalem, Foad
  • 1 Nada, Jalal
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Oracles and decision trees
  • Show More...

  • Refine by Keyword
  • 1 Group Testing
  • 1 Randomized Algorithm
  • 1 Testing decision trees
  • 1 Vector addition system
  • 1 affine net
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2020
  • 1 2022
  • 1 2024

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