Embedded Files
FUN2018 Program
FUN2018 Program
12th June (Tue)
12th June (Tue)
- 19:30-- Welcome Reception
13th June (Wed)
13th June (Wed)
- 09:00--10:00 Invited talk 1- Martin Farach-Colton: Mind the Gap
- 10:00--10:30 Coffee break (30 min.)
- 10:30--11:30 Contributed talks (20 min. x 3)
- Erik Demaine, Isaac Grosof, Jayson Lynch and Mikhail Rudoy: Computational Complexity of Motion Planning of a Robot through Simple Gadgets
- Matteo Almanza, Stefano Leucci and Alessandro Panconesi: Tracks from Hell - when finding a proof may be easier than checking it
- David Eppstein: Making Change in 2048
- 11:30--11:45 Short break (15 min.)
- 11:45--12:45 Contributed talks (20 min. x 3)
- Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny and Sunil Shende: God Save the Queen
- David Eppstein: Faster Evaluation of Subtraction Games
- Naoki Kitamura, Yuya Kawabata and Taisuke Izumi: Uniform Distribution On Pachinko
- 12:45--14:15 Lunch break (90 min.)
- 14:15--15:15 Contributed talks (20 min. x 3)
- Tami Tamir: The Power of One Secret Agent
- Manuel Lafond: The complexity of speedrunning video games
- Michael Coulombe and Jayson Lynch: Cooperating in Video Games? Impossible! Undecideability of Team Multiplayer Games
- 15:15--15:45 Coffee break (30 min.)
- 15:45--16:45 Contributed talks (20 min. x 3)
- Fabio Botler, Andres Cristi, Ruben Hoeksma, Kevin Schewior and Andreas Tonnis: SUPERSET: A (super)natural variant of the card game SET
- Guangqi Cui, John Dickerson, Naveen Durvasula, William Gasarch, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak and Sung Hyun Yoo: A Muffin-Theorem Generator
- Erik D. Demaine, Joshua Lockhart and Jayson Lynch: The Computational Complexity of Portal and Other 3D Video Games
- Banquet
14th June (Thu)
14th June (Thu)
- 09:00--10:00 Contributed talks (20 min. x 3)
- Tatsuya Sasaki, Takaaki Mizuki and Hideaki Sone: Card-Based Zero-Knowledge Proof for Sudoku
- Kei Kimura, Takuya Kamehashi and Toshihiro Fujito: The Fewest Clues Problem of Picross 3D
- Chuzo Iwamoto, Masato Haruishi and Tatsuaki Ibusuki: Herugolf and Makaro are NP-complete
- 10:00--10:30 Coffee break (30 min.)
- 10:30--11:30 Contributed talks (20 min. x 3)
- Florian David Schwahn and Clemens Thielen: The Complexity of Escaping Labyrinths and Enchanted Forests
- Jeffrey Bosboom, Erik D. Demaine and Mikhail Rudoy: Computational Complexity of Generalized Push Fight
- Ronald de Haan and Petra Wolf: Restricted Power -- Computational Complexity Results for Strategic Defense Games
- 11:30--11:45 Short break (15 min.)
- 11:45--12:45 Contributed talks (20 min. x 3)
- Kazumasa Shinagawa and Takaaki Mizuki: Card-based Protocols Using Triangle Cards
- Xavier Bultel, Jannik Dreier, Jean-Guillaume Dumas and Pascal Lafourcade: A Cryptographer's Conspiracy Santa
- Paolo Boldi and Sebastiano Vigna: Kings, Name Days, Lazy Servants and Magic
- 12:45--14:15 Lunch break (90 min.)
- 14:15--15:15 Contributed talks (20 min. x 3)
- Christine Markarian, Heiko Hamann, Friedhelm Meyer Auf der Heide and Mostafa Wahby: Pick, Pack, & Survive: Charging Robots in a Modern Warehouse based on Online Connected Dominating Sets
- Markus Holzer and Jan-Tobias Maurer: Selection Via the Bogo-Method---More on the Analysis of Perversely Awful Randomized Algorithms
- Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe and Dorian Mazauric: How long does it take for all users in a social network to choose their communities?
- Tour
15th June (Fri)
15th June (Fri)
- 09:00--10:00 Invited talk 2 - Kokichi Sugihara: Evolution of Impossible Objects
- 10:00--10:30 Coffee break (30 min.)
- 10:30--11:30 Contributed talks (20 min. x 3)
- Valentin Polishchuk and Leonid Sedov: Gender-aware facility location in multi-gender world
- Davide Bilo, Luciano Guala, Stefano Leucci, Guido Proietti and Mirko Rossi: On the PSPACE-completeness of Peg Duotaire and other Peg-Jumping Games
- Davide Bilo, Luciano Guala, Stefano Leucci and Neeldhara Misra: On the Complexity of TwoDots for Narrow Boards and Few Colors
- 11:30--11:45 Short break (15 min.)
- 11:45--12:45 Contributed talks (20 min. x 3)
- Hans L. Bodlaender and Tom van der Zanden: On the Exact Complexity of Polyomino Packing
- Remy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis and Yota Otachi: How Bad is the Freedom to Flood-It?
- Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch and Mikhail Rudoy: Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
- 12:45-- Lunch
-----
Keynotes of invited talks
Keynotes of invited talks
- Martin Farach-Colton, Rutgers University, USA
Mind the Gap
As a New Yorker, I’m painfully aware of space. There is, after all, nothing more luxurious than empty space! So when it comes to algorithms, I’m all in favor of leaving holes in my data structures. In this talk, I’ll explore the advantages of pampering algorithms with some much needed breathing room.
- Kokichi Sugihara, Meiji University, Japan
Evolution of Impossible Objects
Starting with the 3D realization of impossible figures, we developed various kinds of impossible objects, such as impossible-motion objects, ambiguous cylinders, partly invisible objects, topology-disturbing objects and deformable objects. We show them together with their mathematical background.
FUN2018 Program Outline
FUN2018 Program Outline
Jun 12 (Tue)
- 19:30-- Welcome Reception
Jun 13 (Wed)
- 09:00--10:00 Invited talk 1
- 10:00--10:30 Coffee break (30 min.)
- 10:30--11:30 Contributed talks (20 min. x 3)
- 11:30--11:45 Short break (15 min.)
- 11:45--12:45 Contributed talks (20 min. x 3)
- 12:45--14:15 Lunch break (90 min.)
- 14:15--15:15 Contributed talks (20 min. x 3)
- 15:15--15:45 Coffee break (30 min.)
- 15:45--16:45 Contributed talks (20 min. x 3)
- Banquet
Jun 14 (Thu)
- 09:00--10:00 Contributed talks (20 min. x 3)
- 10:00--10:30 Coffee break (30 min.)
- 10:30--11:30 Contributed talks (20 min. x 3)
- 11:30--11:45 Short break (15 min.)
- 11:45--12:45 Contributed talks (20 min. x 3)
- 12:45--14:15 Lunch break (90 min.)
- 14:15--15:15 Contributed talks (20 min. x 3)
- Tour
Jun 15 (Fri)
- 09:00--10:00 Invited talk 2
- 10:00--10:30 Coffee break (30 min.)
- 10:30--11:30 Contributed talks (20 min. x 3)
- 11:30--11:45 Short break (15 min.)
- 11:45--12:45 Contributed talks (20 min. x 3)
- 12:45-- Lunch
Google Sites
Report abuse