FUN 2018 June 13-15, 2018 - La Maddalena, Italy

9th International Conference on Fun with Algorithms (FUN 2018)



Hiro Ito and Stefano Leonardi and Linda Pagli and Giuseppe Prencipe (Eds.)
ISBN 978-3-95977-067-5, LIPICS Vol. 100 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 39 MB)
Search Publication Server

Authors
  • Abel, Zachary
  • Almanza, Matteo
  • Belmonte, Rémy
  • Bermond, Jean-Claude
  • Bilò, Davide
  • Bodlaender, Hans L.
  • Boldi, Paolo
  • Bosboom, Jeffrey
  • Botler, Fábio
  • Bultel, Xavier
  • Chaintreau, Augustin
  • Coulombe, Michael J.
  • Cristi, Andrés
  • Cui, Guangqi
  • Czyzowicz, Jurek
  • de Haan, Ronald
  • Demaine, Erik D.
  • Dickerson, John
  • Dreier, Jannik
  • Ducoffe, Guillaume
  • Dumas, Jean-Guillaume
  • Durvasula, Naveen
  • Eppstein, David
  • Farach-Colton, Martín
  • Fujito, Toshihiro
  • Gasarch, William
  • Georgiou, Konstantinos
  • Grosof, Isaac
  • Gualà, Luciano
  • Hamann, Heiko
  • Hamilton, Linus
  • Haruishi, Masato
  • Hesterberg, Adam
  • Hoeksma, Ruben
  • Holzer, Markus
  • Ibusuki, Tatsuaki
  • Ito, Hiro
  • Iwamoto, Chuzo
  • Izumi, Taisuke
  • Kamehashi, Takuya
  • Kawabata, Yuya
  • Khosravian Ghadikolaei, Mehdi
  • Killick, Ryan
  • Kimura, Kei
  • Kitamura, Naoki
  • Kiyomi, Masashi
  • Kopinsky, Justin
  • Kranakis, Evangelos
  • Krizanc, Danny
  • Lafond, Manuel
  • Lafourcade, Pascal
  • Lampis, Michael
  • Leonardi, Stefano
  • Leucci, Stefano
  • Lockhart, Joshua
  • Lynch, Jayson
  • Markarian, Christine
  • Maurer, Jan-Tobias
  • Mazauric, Dorian
  • Metz, Erik
  • Meyer auf der Heide, Friedhelm
  • Misra, Neeldhara
  • Mizuki, Takaaki
  • Narayanan, Lata
  • Opatrny, Jaroslav
  • Otachi, Yota
  • Pagli, Linda
  • Panconesi, Alessandro
  • Polishchuk, Valentin
  • Prencipe, Giuseppe
  • Prinz, Jacob
  • Proietti, Guido
  • Raman, Naveen
  • Rossi, Mirko
  • Rudoy, Mikhail
  • Sasaki, Tatsuya
  • Schewior, Kevin
  • Schwahn, Florian D.
  • Sedov, Leonid
  • Shende, Sunil
  • Shinagawa, Kazumasa
  • Smolyak, Daniel
  • Sone, Hideaki
  • Sugihara, Kokichi
  • Tamir, Tami
  • Thielen, Clemens
  • Tönnis, Andreas
  • van der Zanden, Tom C.
  • Vigna, Sebastiano
  • Wahby, Mostafa
  • Wolf, Petra
  • Yoo, Sung Hyun
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Ito, Hiro ; Leonardi, Stefano ; Pagli, Linda ; Prencipe, Giuseppe

    Abstract | Document (417 KB) | BibTeX

    Mind the Gap (Invited Paper)
    Authors: Farach-Colton, Martín

    Abstract | Document (253 KB) | BibTeX

    Evolution of Impossible Objects (Invited Paper)
    Authors: Sugihara, Kokichi

    Abstract | Document (15,706 KB) | BibTeX

    Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
    Authors: Abel, Zachary ; Bosboom, Jeffrey ; Demaine, Erik D. ; Hamilton, Linus ; Hesterberg, Adam ; Kopinsky, Justin ; Lynch, Jayson ; Rudoy, Mikhail

    Abstract | Document (772 KB) | BibTeX

    Tracks from hell - when finding a proof may be easier than checking it
    Authors: Almanza, Matteo ; Leucci, Stefano ; Panconesi, Alessandro

    Abstract | Document (858 KB) | BibTeX

    How Bad is the Freedom to Flood-It?
    Authors: Belmonte, Rémy ; Khosravian Ghadikolaei, Mehdi ; Kiyomi, Masashi ; Lampis, Michael ; Otachi, Yota

    Abstract | Document (581 KB) | BibTeX

    How long does it take for all users in a social network to choose their communities?
    Authors: Bermond, Jean-Claude ; Chaintreau, Augustin ; Ducoffe, Guillaume ; Mazauric, Dorian

    Abstract | Document (761 KB) | BibTeX

    On the Complexity of Two Dots for Narrow Boards and Few Colors
    Authors: Bilò, Davide ; Gualà, Luciano ; Leucci, Stefano ; Misra, Neeldhara

    Abstract | Document (676 KB) | BibTeX

    On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games
    Authors: Bilò, Davide ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido ; Rossi, Mirko

    Abstract | Document (1,286 KB) | BibTeX

    On the Exact Complexity of Polyomino Packing
    Authors: Bodlaender, Hans L. ; van der Zanden, Tom C.

    Abstract | Document (493 KB) | BibTeX

    Kings, Name Days, Lazy Servants and Magic
    Authors: Boldi, Paolo ; Vigna, Sebastiano

    Abstract | Document (490 KB) | BibTeX

    Computational Complexity of Generalized Push Fight
    Authors: Bosboom, Jeffrey ; Demaine, Erik D. ; Rudoy, Mikhail

    Abstract | Document (1,385 KB) | BibTeX

    SUPERSET: A (Super)Natural Variant of the Card Game SET
    Authors: Botler, Fábio ; Cristi, Andrés ; Hoeksma, Ruben ; Schewior, Kevin ; Tönnis, Andreas

    Abstract | Document (540 KB) | BibTeX

    A Cryptographer's Conspiracy Santa
    Authors: Bultel, Xavier ; Dreier, Jannik ; Dumas, Jean-Guillaume ; Lafourcade, Pascal

    Abstract | Document (476 KB) | BibTeX

    Cooperating in Video Games? Impossible! Undecidability of Team Multiplayer Games
    Authors: Coulombe, Michael J. ; Lynch, Jayson

    Abstract | Document (489 KB) | BibTeX

    A Muffin-Theorem Generator
    Authors: Cui, Guangqi ; Dickerson, John ; Durvasula, Naveen ; Gasarch, William ; Metz, Erik ; Prinz, Jacob ; Raman, Naveen ; Smolyak, Daniel ; Yoo, Sung Hyun

    Abstract | Document (478 KB) | BibTeX

    God Save the Queen
    Authors: Czyzowicz, Jurek ; Georgiou, Konstantinos ; Killick, Ryan ; Kranakis, Evangelos ; Krizanc, Danny ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil

    Abstract | Document (985 KB) | BibTeX

    Restricted Power - Computational Complexity Results for Strategic Defense Games
    Authors: de Haan, Ronald ; Wolf, Petra

    Abstract | Document (500 KB) | BibTeX

    Computational Complexity of Motion Planning of a Robot through Simple Gadgets
    Authors: Demaine, Erik D. ; Grosof, Isaac ; Lynch, Jayson ; Rudoy, Mikhail

    Abstract | Document (559 KB) | BibTeX

    The Computational Complexity of Portal and Other 3D Video Games
    Authors: Demaine, Erik D. ; Lockhart, Joshua ; Lynch, Jayson

    Abstract | Document (3,333 KB) | BibTeX

    Faster Evaluation of Subtraction Games
    Authors: Eppstein, David

    Abstract | Document (436 KB) | BibTeX

    Making Change in 2048
    Authors: Eppstein, David

    Abstract | Document (498 KB) | BibTeX

    Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets
    Authors: Hamann, Heiko ; Markarian, Christine ; Meyer auf der Heide, Friedhelm ; Wahby, Mostafa

    Abstract | Document (541 KB) | BibTeX

    Selection Via the Bogo-Method - More on the Analysis of Perversely Awful Randomized Algorithms
    Authors: Holzer, Markus ; Maurer, Jan-Tobias

    Abstract | Document (737 KB) | BibTeX

    Herugolf and Makaro are NP-complete
    Authors: Iwamoto, Chuzo ; Haruishi, Masato ; Ibusuki, Tatsuaki

    Abstract | Document (532 KB) | BibTeX

    The Fewest Clues Problem of Picross 3D
    Authors: Kimura, Kei ; Kamehashi, Takuya ; Fujito, Toshihiro

    Abstract | Document (621 KB) | BibTeX

    Uniform Distribution On Pachinko
    Authors: Kitamura, Naoki ; Kawabata, Yuya ; Izumi, Taisuke

    Abstract | Document (1,404 KB) | BibTeX

    The complexity of speedrunning video games
    Authors: Lafond, Manuel

    Abstract | Document (2,051 KB) | BibTeX

    Gender-Aware Facility Location in Multi-Gender World
    Authors: Polishchuk, Valentin ; Sedov, Leonid

    Abstract | Document (638 KB) | BibTeX

    Card-Based Zero-Knowledge Proof for Sudoku
    Authors: Sasaki, Tatsuya ; Mizuki, Takaaki ; Sone, Hideaki

    Abstract | Document (428 KB) | BibTeX

    The Complexity of Escaping Labyrinths and Enchanted Forests
    Authors: Schwahn, Florian D. ; Thielen, Clemens

    Abstract | Document (3,832 KB) | BibTeX

    Card-based Protocols Using Triangle Cards
    Authors: Shinagawa, Kazumasa ; Mizuki, Takaaki

    Abstract | Document (1,162 KB) | BibTeX

    The Power of One Secret Agent
    Authors: Tamir, Tami

    Abstract | Document (581 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI