Accepted Papers

FUN 2024 accepted papers

• • Yuki Iburi and Ryuhei Uehara. Computational Complexity of Matching Match Puzzle

  • Guillaume Bagan, Eric Duchene, Florian Galliot, Valentin Gledel, Mirjana Mikalacki, Nacim Oijid, Aline Parreau and Milos Stojakovic. Poset Positional Games

  • Xavier Bultel. Physical Ring Signature

  • Reo Eriguchi, Kazumasa Shinagawa and Takao Murakami. Card-based Cryptography Meets Differential Privacy

  • Basile Couëtoux, Bastien Gastaldi and Guyslain Naves. The steady-states of splitter networks

  • Rikhav Shah. Achieving the Highest Possible Elo Rating

  • Antoine Dailly, Pascal Lafourcade and Gaël Marcadet. How did they design this game? Swish: complexity and unplayable positions

  • Jiří Sgall, János Balogh, József Békési, György Dósa, Lars Magnus Hvattum and Zsolt Tuza. No tiling of the 70x70 square with consecutive squares

  • Jaehyun Koo. Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall

  • Mit Hardness Group, Erik D. Demaine, Holden Hall and Jeffery Li. Tetris with Few Piece Types

  • Davide Bilò, Maurizio Fiusco, Luciano Gualà and Stefano Leucci. Swapping Mixed-up Beers to Keep Them Cool

  • Thomas Garrison, Bernardo Subercaseaux and Marijn Heule. PackIt! Gamified Rectangle Packing

  • Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto and Koji Nuida. How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik's Cube

  • Mit Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall and Matias Korman. PSPACE-Hard 2D Super Mario Games: Thirteen Doors

  • Matthias Gehnen and Luca Venier. Online Tetris is not competitive

  • Alex Churchill and Choong Yin Howe. A Programming Language Embedded in Magic: The Gathering

  • Christian Ikenmeyer and Dylan Khangure. Advanced Spikes 'n' Stuff: An NP-hard puzzle game in which all tutorials are efficiently solvable

  • Benjamin Rin and Atze Schipper. Arimaa is PSPACE-hard

  • Benjamin Smith, Sebastian Wild and Leszek Gąsieniec. Polyamorous Scheduling

  • Simone Faro, Francesco Pio Marino, Arianna Pavone, Antonio Scardace and Andrea Moschetto. The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples

  • Kyle Burke, Matthew Ferland, Svenja Huntemannand and Shang-Hua Teng. A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers

  • Gerth Stølting Brodal. Bottom-up Rebalancing Binary Search Trees by Flipping a Coin

  • Davide Bilò, Luca Di Donato, Luciano Gualà and Stefano Leucci. Uniform-Budget Solo Chess with Only Rooks or Only Knights is Hard

  • Benjamin Rin, Marnix Deurloo, Mitchell Donkers, Mieke Maarse and Karen Schutte. Hamilton Paths and Cycles in NP-complete Puzzles

  • Fabrizio Luccio, Linda Pagli and Nicola Santoro. Variations on the Tournament Problem

  • Mit Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz and Naveen Venkat. You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games

  • Mit Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Della Hendrickson and Andy Tockman. ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles

  • Zachary Abel and Della Hendrickson. Baba is Universal

  • Alessandro Panconesi, Pietro Maria Posta and Mirko Giacchini. Coordinating '7 Billion Humans' is hard

  • Philip Bille, Inge Li Gørtz, Martin Farach-Colton and Ivor van der Hoog. Snake in Optimal Space and Time

  • Mit Hardness Group, Della Hendrickson and Andy Tockman. Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants

Computer Science Salon des Refusés 2024 accepted papers

• Victor Miller. Short Programs for Functions on Curves.

• Kai Li. A Proposal to Present the History and Retrospective of “Avoiding the Disk Bottleneck in the Data Domain Deduplication File System”

• Kien Huynh and Valentin Polishchuk. Eating Ice-Cream with a Colander