Volume
LIPIcs, Volume 226
11th International Conference on Fun with Algorithms (FUN 2022)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN)
Publication Details
- published at: 2022-05-23
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-232-7
- DBLP: db/conf/fun/fun2022
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 226, FUN 2022, Complete Volume
Abstract
LIPIcs, Volume 226, FUN 2022, Complete Volume
Cite as
11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1-450, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@Proceedings{fraigniaud_et_al:LIPIcs.FUN.2022,
title = {{LIPIcs, Volume 226, FUN 2022, Complete Volume}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {1--450},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022},
URN = {urn:nbn:de:0030-drops-159693},
doi = {10.4230/LIPIcs.FUN.2022},
annote = {Keywords: LIPIcs, Volume 226, FUN 2022, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fraigniaud_et_al:LIPIcs.FUN.2022.0,
author = {Fraigniaud, Pierre and Uno, Yushi},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {0:i--0:xii},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.0},
URN = {urn:nbn:de:0030-drops-159703},
doi = {10.4230/LIPIcs.FUN.2022.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Pushing Blocks by Sweeping Lines
Abstract
We investigate the reconfiguration of n blocks, or "tokens", in the square grid using line pushes. A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite direction by one unit. Tokens that are in the way of other tokens are displaced in the same direction, as well.
Similar models of manipulating objects using uniform external forces match the mechanics of existing games and puzzles, such as Mega Maze, 2048 and Labyrinth, and have also been investigated in the context of self-assembly, programmable matter and robotic motion planning. The problem of obtaining a given shape from a starting configuration is know to be NP-complete.
We show that, for every n, there are sparse initial configurations of n tokens (i.e., where no two tokens are in the same row or column) that can be compacted into any a×b box such that ab = n. However, only 1×k, 2×k and 3×3 boxes are obtainable from any arbitrary sparse configuration with a matching number of tokens. We also study the problem of rearranging labeled tokens into a configuration of the same shape, but with permuted tokens. For every initial configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.
Cite as
Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta. Pushing Blocks by Sweeping Lines. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1,
author = {A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni},
title = {{Pushing Blocks by Sweeping Lines}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {1:1--1:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.1},
URN = {urn:nbn:de:0030-drops-159719},
doi = {10.4230/LIPIcs.FUN.2022.1},
annote = {Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation}
}
Document
A Practical Algorithm for Chess Unwinnability
Abstract
The FIDE Laws of Chess establish that if a player runs out of time during a game, they lose unless there exists no sequence of legal moves that ends in a checkmate by their opponent, in which case the game is drawn. The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games.
We propose, to the best of our knowledge, the first algorithm for chess unwinnability that is sound, complete and efficient for practical use. We also develop a prototype implementation and evaluate it over the entire Lichess Database (containing more than 3 billion games), successfully identifying all unfairly classified games in the database.
Cite as
Miguel Ambrona. A Practical Algorithm for Chess Unwinnability. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ambrona:LIPIcs.FUN.2022.2,
author = {Ambrona, Miguel},
title = {{A Practical Algorithm for Chess Unwinnability}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {2:1--2:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.2},
URN = {urn:nbn:de:0030-drops-159721},
doi = {10.4230/LIPIcs.FUN.2022.2},
annote = {Keywords: chess, helpmate, unwinnability, timeout, dead position}
}
Document
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude
Abstract
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (first posed in 1999). We also prove PSPACE-completeness of two versions of the recently studied block-moving puzzle game with gravity, Block Dude - a video game dating back to 1994 - featuring either liftable blocks or pushable blocks. Two of our reductions are built on a new framework for "checkable" gadgets, extending the motion-planning-through-gadgets framework to support gadgets that can be misused, provided those misuses can be detected later.
Cite as
Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 3:1-3:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ani_et_al:LIPIcs.FUN.2022.3,
author = {Ani, Joshua and Chung, Lily and Demaine, Erik D. and Diomidov, Yevhenii and Hendrickson, Dylan and Lynch, Jayson},
title = {{Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {3:1--3:30},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.3},
URN = {urn:nbn:de:0030-drops-159737},
doi = {10.4230/LIPIcs.FUN.2022.3},
annote = {Keywords: gadgets, motion planning, hardness of games}
}
Document
Fun Slot Machines and Transformations of Words Avoiding Factors
Abstract
Fun Slot Machines are a variant of the classical ones. Pulling a lever, the player generates a sequence of symbols which are placed on the reels. The machine pays when a given pattern appears in the sequence. The variant consists in trying to transform a losing sequence of symbols in another one, in such a way that the winning pattern does not appear in any intermediate step. The choice of the winning pattern can be crucial; there are "good" and "bad" sequences. The game results in a combinatorial problem on transformations of words avoiding a given pattern as a factor. We investigate "good" and "bad" sequences on a k-ary alphabet and the pairs of words that witness that a word is "bad". A main result is an algorithm to decide whether a word is "bad" or not and to provide a pair of witnesses of minimal length when the word is "bad". It runs in O(n) time with a preprocessing of O(n) time and space to construct an enhanced suffix tree of the word.
Cite as
Marcella Anselmo, Manuela Flores, and Maria Madonia. Fun Slot Machines and Transformations of Words Avoiding Factors. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{anselmo_et_al:LIPIcs.FUN.2022.4,
author = {Anselmo, Marcella and Flores, Manuela and Madonia, Maria},
title = {{Fun Slot Machines and Transformations of Words Avoiding Factors}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {4:1--4:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.4},
URN = {urn:nbn:de:0030-drops-159743},
doi = {10.4230/LIPIcs.FUN.2022.4},
annote = {Keywords: Isometric words, Words avoiding factors, Index of a word, Overlap, Lee distance}
}
Document
Chess Is Hard Even for a Single Player
Abstract
We introduce a generalization of "Solo Chess", a single-player variant of the game that can be played on chess.com. The standard version of the game is played on a regular 8 × 8 chessboard by a single player, with only white pieces, using the following rules: every move must capture a piece, no piece may capture more than 2 times, and if there is a King on the board, it must be the final piece. The goal is to clear the board, i.e, make a sequence of captures after which only one piece is left.
We generalize this game to unbounded boards with n pieces, each of which have a given number of captures that they are permitted to make. We show that Generalized Solo Chess is NP-complete, even when it is played by only rooks that have at most two captures remaining. It also turns out to be NP-complete even when every piece is a queen with exactly two captures remaining in the initial configuration. In contrast, we show that solvable instances of Generalized Solo Chess can be completely characterized when the game is: a) played by rooks on a one-dimensional board, and b) played by pawns with two captures left on a 2D board.
Inspired by Generalized Solo Chess, we also introduce the Graph Capture Game, which involves clearing a graph of tokens via captures along edges. This game subsumes Generalized Solo Chess played by knights. We show that the Graph Capture Game is NP-complete for undirected graphs and DAGs.
Cite as
N.R. Aravind, Neeldhara Misra, and Harshil Mittal. Chess Is Hard Even for a Single Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{aravind_et_al:LIPIcs.FUN.2022.5,
author = {Aravind, N.R. and Misra, Neeldhara and Mittal, Harshil},
title = {{Chess Is Hard Even for a Single Player}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {5:1--5:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.5},
URN = {urn:nbn:de:0030-drops-159753},
doi = {10.4230/LIPIcs.FUN.2022.5},
annote = {Keywords: chess, strategy, board games, NP-complete}
}
Document
Rolling Polyhedra on Tessellations
Abstract
We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation.
Cite as
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. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{baes_et_al:LIPIcs.FUN.2022.6,
author = {Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron},
title = {{Rolling Polyhedra on Tessellations}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {6:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6},
URN = {urn:nbn:de:0030-drops-159761},
doi = {10.4230/LIPIcs.FUN.2022.6},
annote = {Keywords: polyhedra, tilings}
}
Document
Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?
Abstract
Bee extinction is a great risk for humanity. To circumvent this ineluctable disaster, we propose to develop beedroids, i.e., small UAVs mimicking the behaviors of real bees. Those beedroids are endowed with very weak capabilities (short-range visibility sensors, no GPS, light with a few colors, ...). Like real bees, they have to self-organize together into swarms. Beedroid swarms will be deployed in cuboid-shaped greenhouse. Each beedroid swarm will have to indefinitely search for flowers to pollinate in its greenhouse. We model this problem as a perpetual exploration of a 3D grid by a swarm of beedroids. In this paper, we propose two optimal solutions to solve this problem and so to save humanity.
Cite as
Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 7:1-7:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bramas_et_al:LIPIcs.FUN.2022.7,
author = {Bramas, Quentin and Devismes, St\'{e}phane and Durand, Ana\"{i}s and Lafourcade, Pascal and Lamani, Anissa},
title = {{Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {7:1--7:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.7},
URN = {urn:nbn:de:0030-drops-159771},
doi = {10.4230/LIPIcs.FUN.2022.7},
annote = {Keywords: Bee extinction, luminous swarms of beedroids, perpetual flower pollination problem, greenhouse}
}
Document
Priority Queues with Decreasing Keys
Abstract
A priority queue stores a set of items with associated keys and supports the insertion of a new item and extraction of an item with minimum key. In applications like Dijkstra’s single source shortest path algorithm and Prim-Jarník’s minimum spanning tree algorithm, the key of an item can decrease over time. Usually this is handled by either using a priority queue supporting the deletion of an arbitrary item or a dedicated DecreaseKey operation, or by inserting the same item multiple times but with decreasing keys.
In this paper we study what happens if the keys associated with items in a priority queue can decrease over time without informing the priority queue, and how such a priority queue can be used in Dijkstra’s algorithm. We show that binary heaps with bottom-up insertions fail to report items with unchanged keys in correct order, while binary heaps with top-down insertions report items with unchanged keys in correct order. Furthermore, we show that skew heaps, leftist heaps, and priority queues based on linking roots of heap-ordered trees, like pairing heaps, binomial queues and Fibonacci heaps, work correctly with decreasing keys without any modifications. Finally, we show that the post-order heap by Harvey and Zatloukal, a variant of a binary heap with amortized constant time insertions and amortized logarithmic time deletions, works correctly with decreasing keys and is a strong contender for an implicit priority queue supporting decreasing keys in practice.
Cite as
Gerth Stølting Brodal. Priority Queues with Decreasing Keys. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{brodal:LIPIcs.FUN.2022.8,
author = {Brodal, Gerth St{\o}lting},
title = {{Priority Queues with Decreasing Keys}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {8:1--8:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.8},
URN = {urn:nbn:de:0030-drops-159787},
doi = {10.4230/LIPIcs.FUN.2022.8},
annote = {Keywords: priority queue, decreasing keys, post-order heap, Dijkstra’s algorithm}
}
Document
Zero-Knowledge Proof of Knowledge for Peg Solitaire
Abstract
Peg solitaire is a very popular traditional single-player board game, known to be NP-complete. In this paper, we present a zero-knowledge proof of knowledge for solutions of peg solitaire instances. Our proof is straightforward, in the sense that it does not use any reduction to another NP-complete problem, and uses the standard design of sigma protocols. Our construction relies on cryptographic commitments, which can be replaced by envelopes to make the protocol physical. As a side contribution, we introduce the notion of isomorphisms for peg solitaire, which is the key tool of our protocol.
Cite as
Xavier Bultel. Zero-Knowledge Proof of Knowledge for Peg Solitaire. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bultel:LIPIcs.FUN.2022.9,
author = {Bultel, Xavier},
title = {{Zero-Knowledge Proof of Knowledge for Peg Solitaire}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {9:1--9:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.9},
URN = {urn:nbn:de:0030-drops-159798},
doi = {10.4230/LIPIcs.FUN.2022.9},
annote = {Keywords: Zero-Knowledge Proof, Peg Solitaire}
}
Document
Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem
Abstract
The concept of nimbers - a.k.a. Grundy-values or nim-values - is fundamental to combinatorial game theory. Beyond the winnability, nimbers provide a complete characterization of strategic interactions among impartial games in disjunctive sums. In this paper, we consider nimber-preserving reductions among impartial games, which enhance the winnability-preserving reductions in traditional computational characterizations of combinatorial games. We prove that Generalized Geography is complete for the natural class, ℐ^P, of polynomially-short impartial rulesets, under polynomial-time nimber-preserving reductions. We refer to this notion of completeness as Sprague-Grundy-completeness. In contrast, we also show that not every PSPACE-complete ruleset in ℐ^P is Sprague-Grundy-complete for ℐ^P.
By viewing every impartial game as an encoding of its nimber - a succinct game secret richer than its winnability alone - our technical result establishes the following striking cryptography-inspired homomorphic theorem: Despite the PSPACE-completeness of nimber computation for ℐ^P, there exists a polynomial-time algorithm to construct, for any pair of games G₁, G₂ in ℐ^P, a Generalized Geography game G satisfying: nimber(G) = nimber(G₁) ⊕ nimber(G₂).
Cite as
Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{burke_et_al:LIPIcs.FUN.2022.10,
author = {Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
title = {{Nimber-Preserving Reduction: Game Secrets And Homomorphic Sprague-Grundy Theorem}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {10:1--10:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.10},
URN = {urn:nbn:de:0030-drops-159808},
doi = {10.4230/LIPIcs.FUN.2022.10},
annote = {Keywords: Combinatorial Games, Nim, Generalized Geography, Sprague-Grundy Theory, Grundy value, Computational Complexity, Functional-Preserving Reductions}
}
Document
Quantum-Inspired Combinatorial Games: Algorithms and Complexity
Abstract
Recently, quantum concepts inspired a new framework in combinatorial game theory. This transformation uses discrete superpositions to yield beautiful new rulesets with succinct representations that require sophisticated strategies. In this paper, we address the following fundamental questions:
- Complexity Leap: Can this framework transform polynomial-time solvable games into intractable games?
- Complexity Collapse: Can this framework transform PSPACE-complete games into ones with complexity in the lower levels of the polynomial-time hierarchy?
We focus our study on how it affects two extensively studied polynomial-time-solvable games: Nim and Undirected Geography. We prove that both Nim and Undirected Geography make a complexity leap over NP, when starting with superpositions: The former becomes Σ₂^p-hard and the latter becomes PSPACE-complete. We further give an algorithm to prove that from any classical starting position, quantumized Undirected Geography remains polynomial-time solvable. Together they provide a nearly-complete characterization for Undirected Geography. Both our algorithm and its correctness proof require strategic moves and graph contraction to extend the matching-based theory for classical Undirected Geography.
Our constructive proofs for both games highlight the intricacy of this framework. The polynomial time robustness of Undirected Geography in this quantum-inspired setting provides a striking contrast to the recent result that the disjunctive sum of two Undirected Geography games is PSPACE-complete. We give a Σ₂^p-hardness analysis of quantumized Nim, even if there are no pile sizes of more than 1.
Cite as
Kyle W. Burke, Matthew Ferland, and Shang-Hua Teng. Quantum-Inspired Combinatorial Games: Algorithms and Complexity. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{burke_et_al:LIPIcs.FUN.2022.11,
author = {Burke, Kyle W. and Ferland, Matthew and Teng, Shang-Hua},
title = {{Quantum-Inspired Combinatorial Games: Algorithms and Complexity}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {11:1--11:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.11},
URN = {urn:nbn:de:0030-drops-159812},
doi = {10.4230/LIPIcs.FUN.2022.11},
annote = {Keywords: Quantum-Inspired Games, Combinatorial Games, Computational Complexity, Polynomial Hierarchy, \c{c}lass\{PSPACE\}, Nim, Generalized Geography, Snort}
}
Document
Grabbing Olives on Linear Pizzas and Pissaladières
Abstract
In this paper we revisit the problem entitled Sharing a Pizza stated by P. Winkler by considering a new puzzle called Sharing a Pissaladiere. The game is played by two polite coatis Alice and Bob who share a pissaladière (a p×q grid) which is divided into rectangular slices. Alice starts in a corner and then the coatis alternate removing a remaining slice adjacent to at most two other slices. On some slices there are precious olives of Nice and the aim of each coati is to grab the maximum number of olives. We first study the particular case of 1×n grid (i.e. a path) where the game is a graph grabbing game known as Sharing a linear pizza. In that case each player can take only an end vertex of the remaining path. These problems are particular cases of a new class of games called d-degenerate games played on a graph with non negative weights assigned to the vertices with the rule that coatis alternatively take a vertex of degree at most d.
Our main results are the following. We give optimal strategies for paths (linear pizzas) with no two adjacent weighty vertices. We also give a recurrence formula to compute the gains which depend only on the parity of n and of the respective parities of weighty vertices with a complexity in O(h²) where h denotes the number of parity changes in the weighty vertices. When the weights are only {0,1} we reduce the computation of the average number of olives collected by each player to a word counting problem. We solve Sharing a pissaladière with {0,1} weights, when there is one olive or 2 olives. In that case Alice (resp. Bob) grabs almost all the olives if the number of vertices of the grid n = p×q is odd (resp. even). We prove that for a 2×q grid with a fixed number k of olives Bob grabs at least ⌈(k-1)/3⌉ olives and almost always grabs all the k olives.
Cite as
Jean-Claude Bermond, Frédéric Havet, and Michel Cosnard. Grabbing Olives on Linear Pizzas and Pissaladières. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{bermond_et_al:LIPIcs.FUN.2022.12,
author = {Bermond, Jean-Claude and Havet, Fr\'{e}d\'{e}ric and Cosnard, Michel},
title = {{Grabbing Olives on Linear Pizzas and Pissaladi\`{e}res}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {12:1--12:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.12},
URN = {urn:nbn:de:0030-drops-159826},
doi = {10.4230/LIPIcs.FUN.2022.12},
annote = {Keywords: Grabbing game, degenerate graph, path, grid}
}
Document
How Fast Can We Play Tetris Greedily with Rectangular Pieces?
Abstract
Consider a variant of Tetris played on a board of width w and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of O(n) rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction from the Multiphase problem [Pătraşcu, 2010] that on a board of width w = Θ(n), if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time O(n^{1/2-ε}) simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in O(n^{1/2}log^{3/2}n) time on boards of width n^O(1), matching the lower bound up to an n^o(1) factor.
Cite as
Justin Dallant and John Iacono. How Fast Can We Play Tetris Greedily with Rectangular Pieces?. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{dallant_et_al:LIPIcs.FUN.2022.13,
author = {Dallant, Justin and Iacono, John},
title = {{How Fast Can We Play Tetris Greedily with Rectangular Pieces?}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {13:1--13:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.13},
URN = {urn:nbn:de:0030-drops-159839},
doi = {10.4230/LIPIcs.FUN.2022.13},
annote = {Keywords: Tetris, Fine-grained complexity, Dynamic data structures, Axis-aligned rectangles}
}
Document
The Synchronization Game on Subclasses of Automata
Abstract
The notion of synchronization of finite automata is connected to one of the long-standing open problems in combinatorial automata theory, which is Černý’s Conjecture. In this paper, we focus on so-called synchronization games. We will discuss how to present synchronization questions in a playful way. This leads us to study related complexity questions on certain classes of finite automata. More precisely, we consider weakly acyclic, commutative and k-simple idempotent automata. We encounter a number of complexity classes, ranging from L up to PSPACE.
Cite as
Henning Fernau, Carolina Haase, and Stefan Hoffmann. The Synchronization Game on Subclasses of Automata. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 14:1-14:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{fernau_et_al:LIPIcs.FUN.2022.14,
author = {Fernau, Henning and Haase, Carolina and Hoffmann, Stefan},
title = {{The Synchronization Game on Subclasses of Automata}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {14:1--14:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.14},
URN = {urn:nbn:de:0030-drops-159842},
doi = {10.4230/LIPIcs.FUN.2022.14},
annote = {Keywords: Synchronization of finite automata, computational complexity}
}
Document
Making Life More Confusing for Firefighters
Abstract
It is well known that fighting a fire is a hard task. The Firefighter problem asks how to optimally deploy firefighters to defend the vertices of a graph from a fire. This problem is NP-Complete on all but a few classes of graphs. Thankfully, firefighters do not have to work alone, and are often aided by the efforts of good natured civillians who slow the spread of a fire by maintaining firebreaks when they are able. We will show that this help, although well-intentioned, unfortunately makes the optimal deployment of firefighters an even harder problem. To model this scenario we introduce the Temporal Firefighter problem, an extension of Firefighter to temporal graphs. We show that Temporal Firefighter is also NP-Complete, and remains so on all but one of the underlying classes of graphs on which Firefighter is known to have polynomial time solutions. This motivates us to explore making use of the temporal structure of the graph in our search for tractability, and we conclude by presenting an FPT algorithm for Temporal Firefighter with respect to the temporal graph parameter vertex-interval-membership-width.
Cite as
Samuel D. Hand, Jessica Enright, and Kitty Meeks. Making Life More Confusing for Firefighters. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{hand_et_al:LIPIcs.FUN.2022.15,
author = {Hand, Samuel D. and Enright, Jessica and Meeks, Kitty},
title = {{Making Life More Confusing for Firefighters}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {15:1--15:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.15},
URN = {urn:nbn:de:0030-drops-159851},
doi = {10.4230/LIPIcs.FUN.2022.15},
annote = {Keywords: Temporal graphs, Spreading processes, Parameterised complexity}
}
Document
Sorting Balls and Water: Equivalence and Computational Complexity
Abstract
Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP . We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.
Cite as
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. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ito_et_al:LIPIcs.FUN.2022.16,
author = {Ito, Takehiro and Kawahara, Jun and Minato, Shin-ichi and Otachi, Yota and Saitoh, Toshiki and Suzuki, Akira and Uehara, Ryuhei and Uno, Takeaki and Yamanaka, Katsuhisa and Yoshinaka, Ryo},
title = {{Sorting Balls and Water: Equivalence and Computational Complexity}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {16:1--16:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.16},
URN = {urn:nbn:de:0030-drops-159867},
doi = {10.4230/LIPIcs.FUN.2022.16},
annote = {Keywords: Ball sort puzzle, recreational mathematics, sorting pairs in bins, water sort puzzle}
}
Document
Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports
Abstract
Some Olympic sports, like the marathon, are purely feats of human athleticism. But in others such as gymnastics, athletes channel their athleticism into a routine of skills. In these disciplines, designing the highest-scoring routine can be a challenging problem, because the routines are judged via a combination of artistic merit, which is largely subjective, and technical difficulty, which comes with complicated but objective scoring rules. Notably, since the 2006 Code of Points, FIG (International Gymnastics Federation) has sought to make gymnastics scoring more objective by encoding more of the score in those objective technical side of scoring, and in this paper, we show how that push is reflected in the computational complexity of routine optimization.
Here, we analyze the purely-technical component of the scoring rules of routines in 17 different events across 5 Olympic sports. We identify four attributes that classify the common rules found in scoring functions, and, for each combination of attributes, prove hardness results or provide algorithms for designing the highest-scoring routine according to the objective technical component of the scoring functions. Ultimately, we discover that optimal routine construction for events in artistic, rhythmic, and trampoline gymnastics is NP-hard, while optimal routine construction for all other sports is in P.
Cite as
James Koppel and Yun William Yu. Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{koppel_et_al:LIPIcs.FUN.2022.17,
author = {Koppel, James and Yu, Yun William},
title = {{Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {17:1--17:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.17},
URN = {urn:nbn:de:0030-drops-159877},
doi = {10.4230/LIPIcs.FUN.2022.17},
annote = {Keywords: complexity, games, sports}
}
Document
How Brokers Can Optimally Abuse Traders
Abstract
Traders buy and sell financial instruments in hopes of making profit, and brokers are responsible for the transaction. There are several hypotheses and conspiracy theories arguing that in some situations, brokers want their traders to lose money. For instance, a broker may want to protect the positions of a privileged customer. Another example is that some brokers take positions opposite to their traders', in which case they make money whenever their traders lose money. These are reasons for which brokers might manipulate prices in order to maximize the losses of their traders.
In this paper, our goal is to perform this shady task optimally - or at least to check whether this can actually be done algorithmically. Assuming total control over the price of an asset (ignoring the usual aspects of finance such as market conditions, external influence or stochasticity), we show how in quadratic time, given a set of trades specified by a stop-loss and a take-profit price, a broker can find a maximum loss price movement. We also look at an online trade model where broker and trader exchange turns, each trying to make a profit. We show in which condition either side can make a profit, and that the best option for the trader is to never trade.
Cite as
Manuel Lafond. How Brokers Can Optimally Abuse Traders. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lafond:LIPIcs.FUN.2022.18,
author = {Lafond, Manuel},
title = {{How Brokers Can Optimally Abuse Traders}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {18:1--18:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.18},
URN = {urn:nbn:de:0030-drops-159882},
doi = {10.4230/LIPIcs.FUN.2022.18},
annote = {Keywords: Algorithms, trading, graph theory}
}
Document
Wordle Is NP-Hard
Abstract
Wordle is a single-player word-guessing game where the goal is to discover a secret word w that has been chosen from a dictionary D. In order to discover w, the player can make at most 𝓁 guesses, which must also be words from D, all words in D having the same length k. After each guess, the player is notified of the positions in which their guess matches the secret word, as well as letters in the guess that appear in the secret word in a different position. We study the game of Wordle from a complexity perspective, proving NP-hardness of its natural formalization: to decide given a dictionary D and an integer 𝓁 if the player can guarantee to discover the secret word within 𝓁 guesses. Moreover, we prove that hardness holds even over instances where words have length k = 5, and that even in this case it is NP-hard to approximate the minimum number of guesses required to guarantee discovering the secret word. We also present results regarding its parameterized complexity and offer some related open problems.
Cite as
Daniel Lokshtanov and Bernardo Subercaseaux. Wordle Is NP-Hard. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 19:1-19:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{lokshtanov_et_al:LIPIcs.FUN.2022.19,
author = {Lokshtanov, Daniel and Subercaseaux, Bernardo},
title = {{Wordle Is NP-Hard}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {19:1--19:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.19},
URN = {urn:nbn:de:0030-drops-159893},
doi = {10.4230/LIPIcs.FUN.2022.19},
annote = {Keywords: wordle, np-hardness, complexity}
}
Document
Mirror Games Against an Open Book Player
Abstract
Mirror games were invented by Garg and Schnieder (ITCS 2019). Alice and Bob take turns (with Alice playing first) in declaring numbers from the set {1,2, …, 2n}. If a player picks a number that was previously played, that player loses and the other player wins. If all numbers are declared without repetition, the result is a draw. Bob has a simple mirror strategy that assures he won't lose and requires no memory. On the other hand, Garg and Schenier showed that every deterministic Alice needs memory of size linear in n in order to secure a draw.
Regarding probabilistic strategies, previous work showed that a model where Alice has access to a secret random perfect matching over {1,2, …, 2n} allows her to achieve a draw in the game w.p. a least 1-1/n and using only polylog bits of memory.
We show that the requirement for secret bits is crucial: for an "open book" Alice with no secrets (Bob knows her memory but not future coin flips) and memory of at most n/4c bits for any c ≥ 2, there is a Bob that wins w.p. close to 1-{2^{-c/2}}.
Cite as
Roey Magen and Moni Naor. Mirror Games Against an Open Book Player. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{magen_et_al:LIPIcs.FUN.2022.20,
author = {Magen, Roey and Naor, Moni},
title = {{Mirror Games Against an Open Book Player}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {20:1--20:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.20},
URN = {urn:nbn:de:0030-drops-159900},
doi = {10.4230/LIPIcs.FUN.2022.20},
annote = {Keywords: Mirror Games, Space Complexity, Eventown-Oddtown}
}
Document
Fun with FUN
Abstract
The notions of scientific community and research field are central elements for researchers and the articles they publish. We propose to explore the evolution of the FUN conference community since its creation from the articles listed in DBLP, authors, program committees, and advertised themes, by means of a novel symmetric embedding, and carefully crafted software tools. Our results make it possible on the one hand to better understand the evolution of the community, and on the other hand to easily integrate new themes or researchers during future editions.
Cite as
Fabien Mathieu and Sébastien Tixeuil. Fun with FUN. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{mathieu_et_al:LIPIcs.FUN.2022.21,
author = {Mathieu, Fabien and Tixeuil, S\'{e}bastien},
title = {{Fun with FUN}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {21:1--21:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.21},
URN = {urn:nbn:de:0030-drops-159913},
doi = {10.4230/LIPIcs.FUN.2022.21},
annote = {Keywords: Natural Language Processing, Relevance Propagation, Bibliometry, Community, Scientific Fields}
}
Document
All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges
Abstract
You provide us with a matroid and an initial base. We say that a subset of the bases "belongs to us" if we can visit each one via a sequence of base exchanges starting from the initial base. It is well-known that "All your base are belong to us". We refine this classic result by showing that it can be done by a simple greedy algorithm. For example, the spanning trees of a graph can be generated by edge exchanges using the following greedy rule: Minimize the larger label of an edge that enters or exits the current spanning tree and which creates a spanning tree that is new (i.e., hasn't been visited already). Amazingly, this works for any graph, for any labeling of its edges, for any initial spanning tree, and regardless of how you choose the edge with the smaller label in each exchange. Furthermore, by maintaining a small amount of information, we can generate each successive spanning tree without storing the previous trees.
In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by a base exchange. Our base exchange Gray codes apply a prefix-exchange on a prefix-minor of the matroid, and we can generate these orders using "history-free" iterative algorithms. More specifically, we store O(m) bits of data, and use O(m) time per base assuming O(1) time independence and coindependence oracles.
Our work generalizes and extends a number of previous results. For example, the bases of the uniform matroid are combinations, and they belong to us using homogeneous transpositions via an Eades-McKay style order. Similarly, the spanning trees of fan graphs belong to us via face pivot Gray codes, which extends recent results of Cameron, Grubb, and Sawada [Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan, COCOON 2021].
Cite as
Arturo Merino, Torsten Mütze, and Aaron Williams. All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 22:1-22:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{merino_et_al:LIPIcs.FUN.2022.22,
author = {Merino, Arturo and M\"{u}tze, Torsten and Williams, Aaron},
title = {{All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {22:1--22:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.22},
URN = {urn:nbn:de:0030-drops-159928},
doi = {10.4230/LIPIcs.FUN.2022.22},
annote = {Keywords: Matroids, base exchange, Gray codes, combinatorial generation, greedy algorithms, spanning trees}
}
Document
Playing Guess Who with Your Kids
Abstract
Guess who is a two-player search game in which each player chooses a character from a deck of 24 cards, and has to infer the other player’s character by asking yes-no questions. A simple binary search strategy allows the starting player find the opponent’s character by asking 5 questions only, when the opponent is honest.
Real-life observations show that in more realistic scenarios, the game is played against adversaries that do not strictly follow the rules, e.g., kids. Such players might decide to answer all questions at once, answer only part of the questions as they do not know the answers to all, and even lie occasionally. We devise strategies for such scenarios using techniques from error-correcting and erasure codes. This connects to a recent line of work on search problems on graphs and trees with unreliable auxiliary information, and could be of independent interest.
Cite as
Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 23:1-23:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{paz_et_al:LIPIcs.FUN.2022.23,
author = {Paz, Ami and Peterfreund, Liat},
title = {{Playing Guess Who with Your Kids}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {23:1--23:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.23},
URN = {urn:nbn:de:0030-drops-159935},
doi = {10.4230/LIPIcs.FUN.2022.23},
annote = {Keywords: Guess Who?, Binary Search, Error Correcting Codes, Erasure Codes}
}
Document
How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku
Abstract
Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.
Cite as
Suthee Ruangwises and Toshiya Itoh. How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 24:1-24:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
Copy BibTex To Clipboard
@InProceedings{ruangwises_et_al:LIPIcs.FUN.2022.24,
author = {Ruangwises, Suthee and Itoh, Toshiya},
title = {{How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku}},
booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)},
pages = {24:1--24:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-232-7},
ISSN = {1868-8969},
year = {2022},
volume = {226},
editor = {Fraigniaud, Pierre and Uno, Yushi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.24},
URN = {urn:nbn:de:0030-drops-159947},
doi = {10.4230/LIPIcs.FUN.2022.24},
annote = {Keywords: Zero-knowledge proof, Card-based cryptography, Shikaku, Puzzles, Games}
}