Embedded Files
Keynote speakers
John Iacono. Université libre de Bruxelles
Title: Potentially Fun.
Abstract: The potential method of analysis has been the tool of choice for proving amortized running times of algorithms, and in particular, data structures, since its inception more than forty years ago. Coming up with a potential function that works for a given data structure is sometimes seen as some sort of black art, but I prefer to view it as solving a puzzle. In this talk I will try to show via many examples how one develops potential functions for a variety of data structuring problems, both well-known and obscure.
Paolo Ferragina. University of Pisa
Title: The Burrows-Wheeler Transform: 40 years and not feeling it!
Abstract: In this talk I’ll fly over 40 years of research on data structure design based on the Burrows-Wheeler Transform, discuss its impacts on the Computational Biology and Data Compression fields, and its contribution to founding the area of Compressed Data structures. I’ll then try to address the natural question: what can be discovered more about the BWT in the era of LLMs and machine learning?
FUN 2024 Program
FUN 2024 Program
Tuesday, June 4, 2024
18:00 Bus leaves Olbia airport
20:00 Welcome reception at
Hotel Le Nereidi - https://www.lenereidihotel.com/
Wednesday, June 5, 2024
08:30-08:50 Registration
08:50-09:00 Welcome
09:00-10:00 Session chair: Tami Tamir
Keynote speaker: John Iacono. Potentially Fun.
10:00-10:30 Coffee break
Session 1 Session chair: Giuseppe Prencipe
10:30-10:50 Gerth Stølting Brodal. Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
10:50-11:10 MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall and Matias Korman. PSPACE-Hard 2D Super Mario Games: Thirteen Doors
Short Chair-Pilates break 1
11:15-11:35 Philip Bille, Inge Li Gørtz, Martin Farach-Colton and Ivor van der Hoog. Snake in Optimal Space and Time
11:35-11:55 Davide Bilò, Maurizio Fiusco, Luciano Gualà and Stefano Leucci. Swapping Mixed-up Beers to Keep Them Cool
12:00-14:00 Lunch break
Session 2 Session chair: Pascal Lafourcade
14:00-14:20 Reo Eriguchi, Kazumasa Shinagawa and Takao Murakami. Card-based Cryptography Meets Differential Privacy
14:20-14:40 Xavier Bultel. Physical Ring Signature
Short Chair-Pilates break 2
14:45-15:05 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
15:10-15:40 Coffee break
15:40-16:00 Kazumasa Shinagawa, Kazuki Kanai, Kengo Miyamoto and Koji Nuida. How to Covertly and Uniformly Scramble the 15 Puzzle and Rubik's Cube
16:00-16:20 Simone Faro, Francesco Pio Marino, Arianna Pavone, Antonio Scardace and Andrea Moschetto. The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples
16:20-16:40 Benjamin Rin, Marnix Deurloo, Mitchell Donkers, Mieke Maarse and Karen Schutte. Hamilton Paths and Cycles in NP-complete Puzzles
Thursday, June 6, 2024
Session 3 Session chair:Davide Bilò
09:00-09:20 Victor Miller. Short Programs for Functions on Curves: Salon de Refuses
09:20-09:40 Alex Churchill and Choong Yin Howe. A Programming Language Embedded in Magic: The Gathering
09:40-10:00 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
10:00-10:30 Coffee break
Session 4 Session chair: Jiří Sgall
10:30-10:50 Jaehyun Koo. Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
10:50-11:10 Benjamin Rin and Atze Schipper. Arimaa is PSPACE-hard
Short Chair-Pilates break 3
11:15-11:35 Benjamin Smith, Sebastian Wild and Leszek Gąsieniec. Polyamorous Scheduling
11:35-11:55 Zachary Abel and Della Hendrickson. Baba is Universal
12:00-14:00 Lunch break
Session 5 Session chair: Linda Pagli
14:00-14:20 2. Kai Li. Avoiding the Disk Bottleneck in the Data Domain Deduplication File System: Salon de Refuses.
14:20-14:40 Guillaume Bagan, Eric Duchene, Florian Galliot, Valentin Gledel, Mirjana Mikalacki, Nacim Oijid, Aline Parreau and Milos Stojakovic. Poset Positional Games
Short Chair-Pilates break 4
14:45-15:05 Kyle Burke, Matthew Ferland, Svenja Huntemann and Shang-Hua Teng. A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
15:05-15:35 Coffee break
Session 6 Session chair: Nicola Santoro
15:35-15:55 Alessandro Panconesi, Pietro Maria Posta and Mirko Giacchini. Coordinating '7 Billion Humans' is hard
15:55-16:15 Yuki Iburi and Ryuhei Uehara. Computational Complexity of Matching Match Puzzle
16:15-16:35 Rikhav Shah. Achieving the Highest Possible Elo Rating
17:30 Boat Trip
Friday, June 7, 2024
09:00-10:00 Session chair: Andrei Broder
Keynote speaker: Paolo Ferragina.
The Burrows-Wheeler Transform: 40 years and not feeling it!
10:00-10:30 Coffee break
Session 7 Session chair: Tami Tamir
10:30-10:50 Antoine Dailly, Pascal Lafourcade and Gaël Marcadet. How did they design this game? Swish: complexity and unplayable positions
10:50-11:10 Fabrizio Luccio, Linda Pagli and Nicola Santoro. Variations on the Tournament Problem
Short Chair-Pilates break 5
11:15-11:35 Davide Bilò, Luca Di Donato, Luciano Gualà and Stefano Leucci. Uniform-Budget Solo Chess with Only Rooks or Only Knights is Hard
11:35-11:55 Basile Couëtoux, Bastien Gastaldi and Guyslain Naves. The steady-states of splitter networks
12:00-14:00 Lunch break
Session 8 Session chair: Erik Demaine
14:00-14:20 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
14:20-14:40 MIT Hardness Group, Della Hendrickson and Andy Tockman. Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
Short Chair-Pilates break 6
14:45-15:05 Thomas Garrison, Bernardo Subercaseaux and Marijn Heule. PackIt! Gamified Rectangle Packing
15:10: Coffee
20:00 Banquet
Saturday, June 8, 2024
Session 9 Session chair: Paolo Boldi
09:00-09:20 Kien Huynh and Valentin Polishchuk. Eating Ice-Cream with a Colander; Salon de Refuses
09:20-09:40 MIT Hardness Group, Erik D. Demaine, Holden Hall and Jeffery Li. Tetris with Few Piece Types
09:40-10:00 Christian Ikenmeyer and Dylan Khangure. Advanced Spikes 'n' Stuff: An NP-hard puzzle game in which all tutorials are efficiently solvable
Short Chair-Pilates break 7
10:05-10:25 Matthias Gehnen and Luca Venier. Online Tetris is not competitive
10:30-11:00 Coffee and Goodbye
Report abuse