3 Search Results for "Panconesi, Alessandro"


Document
Tracks from hell - when finding a proof may be easier than checking it

Authors: Matteo Almanza, Stefano Leucci, and Alessandro Panconesi

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)


Abstract
We consider the popular smartphone game Trainyard: a puzzle game that requires the player to lay down tracks in order to route colored trains from departure stations to suitable arrival stations. While it is already known [Almanza et al., FUN 2016] that the problem of finding a solution to a given Trainyard instance (i.e., game level) is NP-hard, determining the computational complexity of checking whether a candidate solution (i.e., a track layout) solves the level was left as an open problem. In this paper we prove that this verification problem is PSPACE-complete, thus implying that Trainyard players might not only have a hard time finding solutions to a given level, but they might even be unable to efficiently recognize them.

Cite as

Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Tracks from hell - when finding a proof may be easier than checking it. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 4:1-4:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{almanza_et_al:LIPIcs.FUN.2018.4,
  author =	{Almanza, Matteo and Leucci, Stefano and Panconesi, Alessandro},
  title =	{{Tracks from hell - when finding a proof may be easier than checking it}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{4:1--4:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.4},
  URN =		{urn:nbn:de:0030-drops-87954},
  doi =		{10.4230/LIPIcs.FUN.2018.4},
  annote =	{Keywords: puzzle games, solitaire games, Trainyard, verification}
}
Document
The Distortion of Locality Sensitive Hashing

Authors: Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)


Abstract
Given a pairwise similarity notion between objects, locality sensitive hashing (LSH) aims to construct a hash function family over the universe of objects such that the probability two objects hash to the same value is their similarity. LSH is a powerful algorithmic tool for large-scale applications and much work has been done to understand LSHable similarities, i.e., similarities that admit an LSH. In this paper we focus on similarities that are provably non-LSHable and propose a notion of distortion to capture the approximation of such a similarity by a similarity that is LSHable. We consider several well-known non-LSHable similarities and show tight upper and lower bounds on their distortion. We also experimentally show that our upper bounds translate to e

Cite as

Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli. The Distortion of Locality Sensitive Hashing. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{chierichetti_et_al:LIPIcs.ITCS.2017.54,
  author =	{Chierichetti, Flavio and Kumar, Ravi and Panconesi, Alessandro and Terolli, Erisa},
  title =	{{The Distortion of Locality Sensitive Hashing}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{54:1--54:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.54},
  URN =		{urn:nbn:de:0030-drops-81688},
  doi =		{10.4230/LIPIcs.ITCS.2017.54},
  annote =	{Keywords: locality sensitive hashing, distortion, similarity}
}
Document
Trainyard is NP-hard

Authors: Matteo Almanza, Stefano Leucci, and Alessandro Panconesi

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)


Abstract
Recently, due to the widespread diffusion of smart-phones, mobile puzzle games have experienced a huge increase in their popularity. A successful puzzle has to be both captivating and challenging, and it has been suggested that this features are somehow related to their computational complexity. Indeed, many puzzle games - such as Mah-Jongg, Sokoban, Candy Crush, and 2048, to name a few - are known to be NP-hard. In this paper we consider Trainyard: a popular mobile puzzle game whose goal is to get colored trains from their initial stations to suitable destination stations. We prove that the problem of determining whether there exists a solution to a given Trainyard level is NP. We also provide an implementation of our hardness reduction (see http://trainyard.isnphard.com).

Cite as

Matteo Almanza, Stefano Leucci, and Alessandro Panconesi. Trainyard is NP-hard. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{almanza_et_al:LIPIcs.FUN.2016.2,
  author =	{Almanza, Matteo and Leucci, Stefano and Panconesi, Alessandro},
  title =	{{Trainyard is NP-hard}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.2},
  URN =		{urn:nbn:de:0030-drops-58796},
  doi =		{10.4230/LIPIcs.FUN.2016.2},
  annote =	{Keywords: Complexity of Games, Trainyard}
}
  • Refine by Author
  • 3 Panconesi, Alessandro
  • 2 Almanza, Matteo
  • 2 Leucci, Stefano
  • 1 Chierichetti, Flavio
  • 1 Kumar, Ravi
  • Show More...

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

  • Refine by Keyword
  • 2 Trainyard
  • 1 Complexity of Games
  • 1 distortion
  • 1 locality sensitive hashing
  • 1 puzzle games
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017
  • 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