Program FUN 2020 and FUN 2022
Sunday, May 29, 2022
20:00 Welcome reception at
Hotel Aegusa - www.aegusahotel.it
Monday, May 30, 2022
08:30-08:50 Registration
08:50-09:00 Welcome
09:00-10:00 Keynote speaker: Alkida Balliu (GSSI, Italy). On Locality in Distributed Computing.
10:00-10:30 Coffee break
Session 1 Session Chair: Pierre Fraigniaud
10:30-10:55 Miguel Ambrona. An Efficient Algorithm for Chess Unwinnability
10:55-11:20 N. R. Aravind, Neeldhara Misra and Harshil Mittal. Chess is hard even for a single player
11:20-11:45 Matthew Ferland, Kyle Burke and Shang-Hua Teng. Number-Preserving Reduction: Game Secrets and Homomorphic Sprague-Grundy Theorem
11:45-12:10 Stefan Hoffmann, Henning Fernau and Carolina Haase. The Synchronization Game on Subclasses of Automata
12:10-14:00 Lunch break
Session 2 Session chair: Roberto Grossi
14:00-14:25 Quentin Bramas, Stéphane Devismes and Pascal Lafourcade. Finding Water on Poleless using Melomaniac Myopic Chameleon Robots
14:25-14:50 Adele Rescigno, Luisa Gargano and Gennaro Cordasco. Speeding up Networks Mining via Neighborhood Diversity
14:50-15:15 Trevor Clokie, Thomas Lidbetter, Antonio Molina Lovett, Jeffrey Shallit and Leon Witzman. Computational Fun with Sturdy and Flimsy Numbers
15:15-15:40 Tomasz Idziaszek. Efficient algorithm for multiplication of numbers in Zeckendorf representation
15:40-16:10 Coffee break
Session 3 Session chair: John Iacono
16:10-16:55 William Kuszmaul. Train Tracks with Gaps (Best paper FUN 2020)
16:55-17:20 Josh Brunner and Julian Wellman. An Optimal Algorithm for Online Freeze-tag
17:20-17:45 David Eppstein, Daniel Frishberg and William Maxwell. On the treewidth of Hanoi graphs
Tuesday, May 31, 2022
Session 4 Session chair: Geppino Pucci
09:00-09:25 Bernardo Subercaseaux and Jérémy Barbay. The Computational Complexity of Evil Hangman
09:25-09:50 Alex Churchill, Stella Biderman and Austin Herrick. Magic: the Gathering is Turing Complete
09:50-10:15 Alexander Koch and Stefan Walzer. Foundations for Actively Secure Card-based Cryptography
10:15-10:40 Daiki Miyahara, Leo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao and Hideaki Sone. Card-Based ZKP Protocols for Takuzu and Juosan
10:40-11:15 Coffee break
Session 5 Session Chair: Adele Rescigno
11:15-11:40 Xavier Bultel. Zero-Knowledge Proof of Knowledge for Peg Solitaire
11:40-12:05 Suthee Ruangwises and Toshiya Itoh. How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku
12:05-12:30 Matthew Ferland, Shanghua Teng and Kyle Burke. Quantum-Inspired Combinatorial Games: Algorithms and Complexity
12:30-12:55 Roey Magen and Moni Naor. Mirror Games Against an Open Book Player
Lunch break (lunch on your own)
Afternoon: Social event - boat trip
Wednesday, June 1, 2022
09:00-10:00 Keynote speaker: Miguel Mosteiro (Pace University, USA). Counting in the Dark
10:00-10:30 Coffee break
Session 6 Session chair: Ryuhei Uehara
10:30-10:55 Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson and Jayson Lynch. PSPACE-completeness of Pushing Blocks via Checked Gadgets
10:55-11:20 Bernardo Subercaseaux and Daniel Lokshtanov. Wordle is NP-hard
11:20-11:45 Samuel Hand, Jessica Enright and Kitty Meeks. Making Life More Confusing for Firefighters
11:45-12:10 Marcella Anselmo, Manuela Flores and Maria Madonia. Fun Slot Machines and Transformations of Words avoiding Factors
12:10-14:00 Lunch break
Session 7 Session chair: G. Viglietta
14:00-14:45 Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti and Giacomo Scornavacca. Cutting Bamboo Down to Size (Best paper FUN 2020)
14:45-15:10 Fabian Frei, Peter Rossmanith and David Wehner. An Open Pouring Problem
15:10-15:35 Loïc Crombez, Guilherme da Fonseca and Yan Gerard. Efficient Algorithms for Battleship
15:35-16:00 Coffee break
Session 8 Session Chair: Yushi Uno
16:00-16:25 Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka and Ryo Yoshinaka. Sorting Balls and Water: Equivalence and Computational Complexity
16:25-16:50 Giovanni Viglietta, Hugo Akitaya and Maarten Löffler. Pushing Blocks by Sweeping Lines
16:50-17:15 Jean-Claude Bermond, Michel Cosnard and Frédéric Havet. Grabbing olives on linear pizzas and pissaladières
17:15-17:40 Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids
20:00 Banquet
Thursday, June 2, 2022
Session 9 Session chair: Stefan Langerman
09:00-09:25 Eryk Kopczynski. Hyperbolic Minesweeper is in P
09:25-09:50 Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson and Jayson Lynch. Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets
09:50-10:15 Josh Brunner, Lily Chung, Erik Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl and Avi Zeff. 1 x 1 Rush Hour is PSPACE-complete
10:15-10:45 Coffee break
Session 10 Session Chair: Andrea Pietracaprina
10:45-11:10 Gerth Stølting Brodal. Priority Queues with Decreasing Keys
11:10-11:35 Justin Dallant and John Iacono. How Fast Can We Play Tetris Greedily With Rectangular Pieces?
11:35-12:00 Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno and Aaron Williams. Rolling Polyhedra on Tessellations
12:00-12:25 Arturo Merino, Torsten Mütze and Aaron Williams. All your Bases are Belong to us: Listing all Bases of a Matroid by Greedy Exchanges
12:25-14:00 Lunch break
14:00-15:00 Keynote speaker: Sergio Rajsbaum (UNAM, Mexico). The science of perspectives: from coordinating insecure lovers to the impossibility of democracy
15:00-15:30 Coffee break
Session 11 Session chair: Alkida Balliu
15:30-15:55 James Koppel and Yun William Yu. Skiing is Easy, Gymnastics is Hard: Complexity of Routine Construction in Olympic Sports
15:55-16:20 Fabien Mathieu and Sebastien Tixeuil. Fun with FUN
16:20-16:45 Manuel Lafond. How Brokers can Optimally Abuse Traders
16:45-17:10 Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade and Anissa Lamani. How Luminous Autonomous Swarms of UAVs can save the World?
17:10-17:35 G.W. van der Heijden, Irina Kostitsyna, Thomas Brocken, Lloyd E. Lo-Wong and Remco J. A. Surtel. Multi-robot motion planning of k-colored discs is PSPACE-hard