1 Search Results for "Mosaad, Hagar"


Document
ARRIVAL: Next Stop in CLS

Authors: Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
We study the computational complexity of Arrival, a zero-player game on n-vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matousek, and Welzl. They showed that the problem of deciding termination of this game is contained in NP n coNP. Karthik C. S. recently introduced a search variant of Arrival and showed that it is in the complexity class PLS. In this work, we significantly improve the known upper bounds for both the decision and the search variants of Arrival. First, we resolve a question suggested by Dohrau et al. and show that the decision variant of Arrival is in UP n coUP. Second, we prove that the search variant of Arrival is contained in CLS. Third, we give a randomized O(1.4143^n)-time algorithm to solve both variants. Our main technical contributions are (a) an efficiently verifiable characterization of the unique witness for termination of the Arrival game, and (b) an efficient way of sampling from the state space of the game. We show that the problem of finding the unique witness is contained in CLS, whereas it was previously conjectured to be FPSPACE-complete. The efficient sampling procedure yields the first algorithm for the problem that has expected runtime O(c^n) with c<2.

Cite as

Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: Next Stop in CLS. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.ICALP.2018.60,
  author =	{G\"{a}rtner, Bernd and Hansen, Thomas Dueholm and Hub\'{a}cek, Pavel and Kr\'{a}l, Karel and Mosaad, Hagar and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{ARRIVAL: Next Stop in CLS}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{60:1--60:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.60},
  URN =		{urn:nbn:de:0030-drops-90641},
  doi =		{10.4230/LIPIcs.ICALP.2018.60},
  annote =	{Keywords: CLS, switch graphs, zero-player game, UP n coUP}
}
  • Refine by Author
  • 1 Gärtner, Bernd
  • 1 Hansen, Thomas Dueholm
  • 1 Hubácek, Pavel
  • 1 Král, Karel
  • 1 Mosaad, Hagar
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 CLS
  • 1 UP n coUP
  • 1 switch graphs
  • 1 zero-player game

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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