Volume
LIPIcs, Volume 157
10th International Conference on Fun with Algorithms (FUN 2021)
-
Part of:
Series:
Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN)
Publication Details
- published at: 2020-09-16
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-145-0
- DBLP: db/conf/fun/fun2021
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 157, FUN 2021, Complete Volume
Abstract
LIPIcs, Volume 157, FUN 2021, Complete Volume
Cite as
10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 1-416, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@Proceedings{farachcolton_et_al:LIPIcs.FUN.2021,
title = {{LIPIcs, Volume 157, FUN 2021, Complete Volume}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {1--416},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021},
URN = {urn:nbn:de:0030-drops-127602},
doi = {10.4230/LIPIcs.FUN.2021},
annote = {Keywords: LIPIcs, Volume 157, FUN 2021, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{farachcolton_et_al:LIPIcs.FUN.2021.0,
author = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {0:i--0:xvi},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.0},
URN = {urn:nbn:de:0030-drops-127613},
doi = {10.4230/LIPIcs.FUN.2021.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Tatamibari Is NP-Complete
Abstract
In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an m x n grid of cells, where each cell possibly contains a clue among ⊞, ⊟, ◫. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing ⊞ are square, rectangles containing ⊟ are strictly longer horizontally than vertically, rectangles containing ◫ are strictly longer vertically than horizontally, and no four rectangles share a corner. We prove this puzzle NP-complete, establishing a Nikoli gap of 16 years. Along the way, we introduce a gadget framework for proving hardness of similar puzzles involving area coverage, and show that it applies to an existing NP-hardness proof for Spiral Galaxies. We also present a mathematical puzzle font for Tatamibari.
Cite as
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch. Tatamibari Is NP-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{adler_et_al:LIPIcs.FUN.2021.1,
author = {Adler, Aviv and Bosboom, Jeffrey and Demaine, Erik D. and Demaine, Martin L. and Liu, Quanquan C. and Lynch, Jayson},
title = {{Tatamibari Is NP-Complete}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {1:1--1:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.1},
URN = {urn:nbn:de:0030-drops-127624},
doi = {10.4230/LIPIcs.FUN.2021.1},
annote = {Keywords: Nikoli puzzles, NP-hardness, rectangle covering}
}
Document
Collaborative Procrastination
Abstract
The problem of inconsistent planning in decision making, which leads to undesirable effects such as procrastination, has been studied in the behavioral-economics literature, and more recently in the context of computational behavioral models. Individuals, however, do not function in isolation, and successful projects most often rely on team work. Team performance does not depend only on the skills of the individual team members, but also on other collective factors, such as team spirit and cohesion. It is not an uncommon situation (for instance, experienced by the authors while working on this paper) that a hard-working individual has the capacity to give a good example to her team-mates and motivate them to work harder.
In this paper we adopt the model of Kleinberg and Oren (EC'14) on time-inconsistent planning, and extend it to account for the influence of procrastination within the members of a team. Our first contribution is to model collaborative work so that the relative progress of the team members, with respect to their respective subtasks, motivates (or discourages) them to work harder. We compare the total cost of completing a team project when the team members communicate with each other about their progress, with the corresponding cost when they work in isolation. Our main result is a tight bound on the ratio of these two costs, under mild assumptions. We also show that communication can either increase or decrease the total cost.
We also consider the problem of assigning subtasks to team members, with the objective of minimizing the negative effects of collaborative procrastination. We show that whereas a simple problem of forming teams of two members can be solved in polynomial time, the problem of assigning n tasks to n agents is NP-hard.
Cite as
Aris Anagnostopoulos, Aristides Gionis, and Nikos Parotsidis. Collaborative Procrastination. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{anagnostopoulos_et_al:LIPIcs.FUN.2021.2,
author = {Anagnostopoulos, Aris and Gionis, Aristides and Parotsidis, Nikos},
title = {{Collaborative Procrastination}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {2:1--2:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.2},
URN = {urn:nbn:de:0030-drops-127634},
doi = {10.4230/LIPIcs.FUN.2021.2},
annote = {Keywords: time-inconsistent planning, computational behavioral science, collaborative work, collaborative environments}
}
Document
Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets
Abstract
A door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "open" and "close" tunnel sets the gadget’s state to open and closed, respectively, while the "traverse" tunnel can be traversed if and only if the door is in the open state. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of such door gadgets, removing the traditional need for crossover gadgets and thereby simplifying past PSPACE-hardness proofs of Lemmings and Nintendo games Super Mario Bros., Legend of Zelda, and Donkey Kong Country. Our result holds in all but one of the possible local planar embedding of the open, close, and traverse tunnels within a door gadget; in the one remaining case, we prove NP-hardness.
We also introduce and analyze a simpler type of door gadget, called the self-closing door. This gadget has two states and only two tunnels, similar to the "open" and "traverse" tunnels of doors, except that traversing the traverse tunnel also closes the door. In a variant called the symmetric self-closing door, the "open" tunnel can be traversed if and only if the door is closed. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar assembly of either type of self-closing door. Then we apply this framework to prove new PSPACE-hardness results for several 3D Mario games and Sokobond.
Cite as
Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yenhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{ani_et_al:LIPIcs.FUN.2021.3,
author = {Ani, Joshua and Bosboom, Jeffrey and Demaine, Erik D. and Diomidov, Yenhenii and Hendrickson, Dylan and Lynch, Jayson},
title = {{Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {3:1--3:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.3},
URN = {urn:nbn:de:0030-drops-127642},
doi = {10.4230/LIPIcs.FUN.2021.3},
annote = {Keywords: gadgets, motion planning, hardness of games}
}
Document
Taming the Knight’s Tour: Minimizing Turns and Crossings
Abstract
We introduce two new metrics of "simplicity" for knight’s tours: the number of turns and the number of crossings. We give a novel algorithm that produces tours with 9.5n+O(1) turns and 13n+O(1) crossings on a n× n board, and we show lower bounds of (6-ε)n and 4n-O(1) on the respective problems of minimizing these metrics. Hence, our algorithm achieves approximation ratios of 19/12+o(1) and 13/4+o(1). We generalize our techniques to rectangular boards, high-dimensional boards, symmetric tours, odd boards with a missing corner, and tours for (1,4)-leapers. In doing so, we show that these extensions also admit a constant approximation ratio on the minimum number of turns, and on the number of crossings in most cases.
Cite as
Juan Jose Besa, Timothy Johnson, Nil Mamano, and Martha C. Osegueda. Taming the Knight’s Tour: Minimizing Turns and Crossings. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{besa_et_al:LIPIcs.FUN.2021.4,
author = {Besa, Juan Jose and Johnson, Timothy and Mamano, Nil and Osegueda, Martha C.},
title = {{Taming the Knight’s Tour: Minimizing Turns and Crossings}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {4:1--4:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.4},
URN = {urn:nbn:de:0030-drops-127654},
doi = {10.4230/LIPIcs.FUN.2021.4},
annote = {Keywords: Graph Drawing, Chess, Hamiltonian Cycle, Approximation Algorithms}
}
Document
Cutting Bamboo down to Size
Abstract
This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house.
The garden consists of n bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i.e., the maximum height ever reached by a bamboo.
Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O(log n) and 4 for the best choice of x = 2, respectively. We prove the first constant upper bound of 9 for Reduce-Max and improve the one for Reduce-Fastest(x) to (3+√5)/2 < 2.62 for x = 1+1/√5.
Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).
Cite as
Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Giacomo Scornavacca. Cutting Bamboo down to Size. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bilo_et_al:LIPIcs.FUN.2021.5,
author = {Bil\`{o}, Davide and Gual\`{a}, Luciano and Leucci, Stefano and Proietti, Guido and Scornavacca, Giacomo},
title = {{Cutting Bamboo down to Size}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {5:1--5:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.5},
URN = {urn:nbn:de:0030-drops-127663},
doi = {10.4230/LIPIcs.FUN.2021.5},
annote = {Keywords: bamboo garden trimming, trimming oracles, approximation algorithms, pinwheel scheduling}
}
Document
Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots
Abstract
In 2042, the exoplanet exploration program, launched in 2014 by NASA, finally discovers a new exoplanet so-called Poleless, due to the fact that it is not subject to any magnetism. A new generation of autonomous mobile robots, called M2C (for Melomaniac Myopic Chameleon), have been designed to find water on Poleless. To address this problem, we investigate optimal (w.r.t., visibility range and number of used colors) solutions to the infinite grid exploration problem (IGE) by a small team of M2C robots. Our first result shows that minimizing the visibility range and the number of used colors are two orthogonal issues: it is impossible to design a solution to the IGE problem that is optimal w.r.t. both parameters simultaneously. Consequently, we address optimality of these two criteria separately by proposing two algorithms; the former being optimal in terms of visibility range, the latter being optimal in terms of number of used colors. It is worth noticing that these two algorithms use a very small number of robots, respectively six and eight.
Cite as
Quentin Bramas, Pascal Lafourcade, and Stéphane Devismes. Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{bramas_et_al:LIPIcs.FUN.2021.6,
author = {Bramas, Quentin and Lafourcade, Pascal and Devismes, St\'{e}phane},
title = {{Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {6:1--6:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.6},
URN = {urn:nbn:de:0030-drops-127674},
doi = {10.4230/LIPIcs.FUN.2021.6},
annote = {Keywords: Luminous Robots, Grid, Infinite Exploration, Treasure Search Problem}
}
Document
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete
Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as
Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
author = {Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
title = {{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {7:1--7:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7},
URN = {urn:nbn:de:0030-drops-127681},
doi = {10.4230/LIPIcs.FUN.2021.7},
annote = {Keywords: puzzles, sliding blocks, PSPACE-hardness}
}
Document
An Optimal Algorithm for Online Freeze-Tag
Abstract
In the freeze-tag problem, one active robot must wake up many frozen robots. The robots are considered as points in a metric space, where active robots move at a constant rate and activate other robots by visiting them. In the (time-dependent) online variant of the problem, each frozen robot is not revealed until a specified time. Hammar, Nilsson, and Persson have shown that no online algorithm can achieve a competitive ratio better than 7/3 for online freeze-tag, and posed the question of whether an O(1)-competitive algorithm exists. We provide a (1+√2)-competitive algorithm for online time-dependent freeze-tag, and show that this is the best possible: there does not exist an algorithm which achieves a lower competitive ratio on every metric space.
Cite as
Josh Brunner and Julian Wellman. An Optimal Algorithm for Online Freeze-Tag. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 8:1-8:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{brunner_et_al:LIPIcs.FUN.2021.8,
author = {Brunner, Josh and Wellman, Julian},
title = {{An Optimal Algorithm for Online Freeze-Tag}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {8:1--8:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.8},
URN = {urn:nbn:de:0030-drops-127693},
doi = {10.4230/LIPIcs.FUN.2021.8},
annote = {Keywords: Online algorithm, competitive ratio, freeze-tag}
}
Document
Magic: The Gathering Is Turing Complete
Abstract
Magic: The Gathering is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world Magic is at least as hard as the Halting Problem. This provides a positive answer to the question "is there a real-world game where perfect play is undecidable under the rules in which it is typically played?", a question that has been open for a decade [David Auger and Oliver Teytaud, 2012; Erik D. Demaine and Robert A. Hearn, 2009]. To do this, we present a methodology for embedding an arbitrary Turing machine into a game of Magic such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real Magic is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting.
Cite as
Alex Churchill, Stella Biderman, and Austin Herrick. Magic: The Gathering Is Turing Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{churchill_et_al:LIPIcs.FUN.2021.9,
author = {Churchill, Alex and Biderman, Stella and Herrick, Austin},
title = {{Magic: The Gathering Is Turing Complete}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {9:1--9:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.9},
URN = {urn:nbn:de:0030-drops-127706},
doi = {10.4230/LIPIcs.FUN.2021.9},
annote = {Keywords: Turing machines, computability theory, Magic: the Gathering, two-player games}
}
Document
Computational Fun with Sturdy and Flimsy Numbers
Abstract
Following Stolarsky, we say that a natural number n is flimsy in base b if some positive multiple of n has smaller digit sum in base b than n does; otherwise it is sturdy . We develop algorithmic methods for the study of sturdy and flimsy numbers.
We provide some criteria for determining whether a number is sturdy. Focusing on the case of base b = 2, we study the computational problem of checking whether a given number is sturdy, giving several algorithms for the problem. We find two additional, previously unknown sturdy primes. We develop a method for determining which numbers with a fixed number of 0’s in binary are flimsy. Finally, we develop a method that allows us to estimate the number of k-flimsy numbers with n bits, and we provide explicit results for k = 3 and k = 5. Our results demonstrate the utility (and fun) of creating algorithms for number theory problems, based on methods of automata theory.
Cite as
Trevor Clokie, Thomas F. Lidbetter, Antonio J. Molina Lovett, Jeffrey Shallit, and Leon Witzman. Computational Fun with Sturdy and Flimsy Numbers. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{clokie_et_al:LIPIcs.FUN.2021.10,
author = {Clokie, Trevor and Lidbetter, Thomas F. and Molina Lovett, Antonio J. and Shallit, Jeffrey and Witzman, Leon},
title = {{Computational Fun with Sturdy and Flimsy Numbers}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {10:1--10:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.10},
URN = {urn:nbn:de:0030-drops-127715},
doi = {10.4230/LIPIcs.FUN.2021.10},
annote = {Keywords: sturdy number, flimsy number, context-free grammar, finite automaton, enumeration}
}
Document
Efficient Algorithms for Battleship
Abstract
We consider an algorithmic problem inspired by the Battleship game. In the variant of the problem that we investigate, there is a unique ship of shape S ⊂ ℤ² which has been translated in the lattice ℤ². We assume that a player has already hit the ship with a first shot and the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. While the player knows the shape S, which position of S has been hit is not known.
Given a shape S of n lattice points, the minimum number of misses that can be achieved in the worst case by any algorithm is called the Battleship complexity of the shape S and denoted c(S). We prove three bounds on c(S), each considering a different class of shapes. First, we have c(S) ≤ n-1 for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide an algorithm that shows that c(S) = O(log n) if S is an HV-convex polyomino. Third, we provide an algorithm that shows that c(S) = O(log log n) if S is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.
Cite as
Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{crombez_et_al:LIPIcs.FUN.2021.11,
author = {Crombez, Lo\"{i}c and da Fonseca, Guilherme D. and Gerard, Yan},
title = {{Efficient Algorithms for Battleship}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.11},
URN = {urn:nbn:de:0030-drops-127728},
doi = {10.4230/LIPIcs.FUN.2021.11},
annote = {Keywords: Polyomino, digital geometry, decision tree, lattice, HV-convexity, convexity}
}
Document
A Phase Transition in Minesweeper
Abstract
We study the average-case complexity of the classic Minesweeper game in which players deduce the locations of mines on a two-dimensional lattice. Playing Minesweeper is known to be co-NP-complete. We show empirically that Minesweeper exhibits a phase transition analogous to the well-studied SAT phase transition. Above the critical mine density it becomes almost impossible to play Minesweeper by logical inference. We use a reduction to Boolean unsatisfiability to characterize the hardness of Minesweeper instances, and show that the hardness peaks at the phase transition. Furthermore, we demonstrate algorithmic barriers at the phase transition for polynomial-time approaches to Minesweeper inference. Finally, we comment on expectations for the asymptotic behavior of the phase transition.
Cite as
Ross Dempsey and Charles Guinn. A Phase Transition in Minesweeper. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 12:1-12:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{dempsey_et_al:LIPIcs.FUN.2021.12,
author = {Dempsey, Ross and Guinn, Charles},
title = {{A Phase Transition in Minesweeper}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {12:1--12:10},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.12},
URN = {urn:nbn:de:0030-drops-127735},
doi = {10.4230/LIPIcs.FUN.2021.12},
annote = {Keywords: Complexity of Games, Minesweeper}
}
Document
On the Treewidth of Hanoi Graphs
Abstract
The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.
Cite as
David Eppstein, Daniel Frishberg, and William Maxwell. On the Treewidth of Hanoi Graphs. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{eppstein_et_al:LIPIcs.FUN.2021.13,
author = {Eppstein, David and Frishberg, Daniel and Maxwell, William},
title = {{On the Treewidth of Hanoi Graphs}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {13:1--13:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.13},
URN = {urn:nbn:de:0030-drops-127741},
doi = {10.4230/LIPIcs.FUN.2021.13},
annote = {Keywords: Hanoi graph, Treewidth, Graph separators, Kneser graph, Vertex expansion, Haven, Tensor product}
}
Document
An Open Pouring Problem
Abstract
We analyze a little riddle that has challenged mathematicians for half a century.
Imagine three clubs catering to people with some niche interest. Everyone willing to join a club has done so and nobody new will pick up this eccentric hobby for the foreseeable future, thus the mutually exclusive clubs compete for a common constituency. Members are highly invested in their chosen club; only a targeted campaign plus prolonged personal persuasion can convince them to consider switching. Even then, they will never be enticed into a bigger group as they naturally pride themselves in avoiding the mainstream. Therefore each club occasionally starts a campaign against a larger competitor and sends its own members out on a recommendation program. Each will win one person over; the small club can thus effectively double its own numbers at the larger one’s expense.
Is there always a risk for one club to wind up with zero members, forcing it out of business? If so, how many campaign cycles will this take?
Cite as
Fabian Frei, Peter Rossmanith, and David Wehner. An Open Pouring Problem. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 14:1-14:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{frei_et_al:LIPIcs.FUN.2021.14,
author = {Frei, Fabian and Rossmanith, Peter and Wehner, David},
title = {{An Open Pouring Problem}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {14:1--14:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.14},
URN = {urn:nbn:de:0030-drops-127751},
doi = {10.4230/LIPIcs.FUN.2021.14},
annote = {Keywords: Pitcher Pouring Problem, Water Jug Riddle, Water Bucket Problem, Vessel Puzzle, Complexity, Die Hard}
}
Document
Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard
Abstract
In the problem of multi-robot motion planning, a group of robots, placed in a polygonal domain with obstacles, must be moved from their starting positions to a set of target positions. We consider the specific case of unlabeled disc robots of two different sizes. That is, within one class of robots, where a class is given by the robots' size, any robot can be moved to any of the corresponding target positions. We prove that the decision problem of whether there exists a schedule moving the robots to the target positions is PSPACE-hard.
Cite as
Thomas Brocken, G. Wessel van der Heijden, Irina Kostitsyna, Lloyd E. Lo-Wong, and Remco J. A. Surtel. Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{brocken_et_al:LIPIcs.FUN.2021.15,
author = {Brocken, Thomas and van der Heijden, G. Wessel and Kostitsyna, Irina and Lo-Wong, Lloyd E. and Surtel, Remco J. A.},
title = {{Multi-Robot Motion Planning of k-Colored Discs Is PSPACE-Hard}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {15:1--15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.15},
URN = {urn:nbn:de:0030-drops-127769},
doi = {10.4230/LIPIcs.FUN.2021.15},
annote = {Keywords: Disc-robot motion planning, algorithmic complexity, PSPACE-hard}
}
Document
Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation
Abstract
In the Zeckendorf representation an integer is expressed as a sum of Fibonacci numbers in which no two are consecutive. We show O(n log n) algorithm for multiplication of two n-digit numbers in Zeckendorf representation.
For this purpose we investigate a relationship between the numeral system using Zeckendorf representations and the golden ratio numeral system. We also show O(n) algorithms for converting numbers between these systems.
Cite as
Tomasz Idziaszek. Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 16:1-16:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{idziaszek:LIPIcs.FUN.2021.16,
author = {Idziaszek, Tomasz},
title = {{Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {16:1--16:9},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.16},
URN = {urn:nbn:de:0030-drops-127770},
doi = {10.4230/LIPIcs.FUN.2021.16},
annote = {Keywords: Fibonacci numbers, Zeckendorf representation, multiplication algorithm, Fast Fourier Transform, golden ratio numeral system, Lucas numbers}
}
Document
Foundations for Actively Secure Card-Based Cryptography
Abstract
Card-based cryptography, as first proposed by den Boer [den Boer, 1989], enables secure multiparty computation using only a deck of playing cards. Many protocols as of yet come with an “honest-but-curious” disclaimer. However, modern cryptography aims to provide security also in the presence of active attackers that deviate from the protocol description. In the few places where authors argue for the active security of their protocols, this is done ad-hoc and restricted to the concrete operations needed, often using additional physical tools, such as envelopes or sliding cover boxes. This paper provides the first systematic approach to active security in card-based protocols.
The main technical contribution concerns shuffling operations. A shuffle randomly permutes the cards according to a well-defined distribution but hides the chosen permutation from the players. We show how the large and natural class of uniform closed shuffles, which are shuffles that select a permutation uniformly at random from a permutation group, can be implemented using only a linear number of helping cards. This ensures that any protocol in the model of Mizuki and Shizuya [Mizuki and Shizuya, 2014] can be realized in an actively secure fashion, as long as it is secure in this abstract model and restricted to uniform closed shuffles. Uniform closed shuffles are already sufficient for securely computing any circuit [Mizuki and Sone, 2009]. In the process, we develop a more concrete model for card-based cryptographic protocols with two players, which we believe to be of independent interest.
Cite as
Alexander Koch and Stefan Walzer. Foundations for Actively Secure Card-Based Cryptography. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 17:1-17:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{koch_et_al:LIPIcs.FUN.2021.17,
author = {Koch, Alexander and Walzer, Stefan},
title = {{Foundations for Actively Secure Card-Based Cryptography}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {17:1--17:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.17},
URN = {urn:nbn:de:0030-drops-127786},
doi = {10.4230/LIPIcs.FUN.2021.17},
annote = {Keywords: Card-Based Protocols, Card Shuffling, Secure Multiparty Computation, Active Security, Cryptography without Computers}
}
Document
Hyperbolic Minesweeper Is in P
Abstract
We show that, while Minesweeper is NP-complete, its hyperbolic variant is in P. Our proof does not rely on the rules of Minesweeper, but is valid for any puzzle based on satisfying local constraints on a graph embedded in the hyperbolic plane.
Cite as
Eryk Kopczyński. Hyperbolic Minesweeper Is in P. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 18:1-18:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kopczynski:LIPIcs.FUN.2021.18,
author = {Kopczy\'{n}ski, Eryk},
title = {{Hyperbolic Minesweeper Is in P}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {18:1--18:7},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.18},
URN = {urn:nbn:de:0030-drops-127797},
doi = {10.4230/LIPIcs.FUN.2021.18},
annote = {Keywords: Minesweeper}
}
Document
Train Tracks with Gaps
Abstract
We identify a tradeoff curve between the number of wheels on a train car, and the amount of track that must be installed in order to ensure that the train car is supported by the track at all times. The goal is to build an elevated track that covers some large distance 𝓁, but that consists primarily of gaps, so that the total amount of feet of train track that is actually installed is only a small fraction of 𝓁. In order so that the train track can support the train at all points, the requirement is that as the train drives across the track, at least one set of wheels from the rear quarter and at least one set of wheels from the front quarter of the train must be touching the track at all times.
We show that, if a train car has n sets of wheels evenly spaced apart in its rear and n sets of wheels evenly spaced apart in its front, then it is possible to build a train track that supports the train car but uses only Θ(𝓁 / n) feet of track. We then consider what happens if the wheels on the train car are not evenly spaced (and may even be configured adversarially). We show that for any configuration of the train car, with n wheels in each of the front and rear quarters of the car, it is possible to build a track that supports the car for distance 𝓁 and uses only O((𝓁 log n)/n) feet of track. Additionally, we show that there exist configurations of the train car for which this tradeoff curve is asymptotically optimal. Both the upper and lower bounds are achieved via applications of the probabilistic method.
The algorithms and lower bounds in this paper provide simple illustrative examples of many of the core techniques in probabilistic combinatorics and randomized algorithms. These include the probabilistic method with alterations, the use of McDiarmid’s inequality within the probabilistic method, the algorithmic Lovász Local Lemma, the min-hash technique, and the method of conditional probabilities.
Cite as
William Kuszmaul. Train Tracks with Gaps. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{kuszmaul:LIPIcs.FUN.2021.19,
author = {Kuszmaul, William},
title = {{Train Tracks with Gaps}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {19:1--19:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.19},
URN = {urn:nbn:de:0030-drops-127800},
doi = {10.4230/LIPIcs.FUN.2021.19},
annote = {Keywords: probabilistic method, algorithms, trains, Lov\'{a}sz Local Lemma, McDiarmid’s Inequality}
}
Document
Card-Based ZKP Protocols for Takuzu and Juosan
Abstract
Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
Cite as
Daiki Miyahara, Léo Robert, Pascal Lafourcade, So Takeshige, Takaaki Mizuki, Kazumasa Shinagawa, Atsuki Nagao, and Hideaki Sone. Card-Based ZKP Protocols for Takuzu and Juosan. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{miyahara_et_al:LIPIcs.FUN.2021.20,
author = {Miyahara, Daiki and Robert, L\'{e}o and Lafourcade, Pascal and Takeshige, So and Mizuki, Takaaki and Shinagawa, Kazumasa and Nagao, Atsuki and Sone, Hideaki},
title = {{Card-Based ZKP Protocols for Takuzu and Juosan}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {20:1--20:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.20},
URN = {urn:nbn:de:0030-drops-127817},
doi = {10.4230/LIPIcs.FUN.2021.20},
annote = {Keywords: Zero-knowledge proof, Card-based cryptography, Takuzu, Juosan}
}
Document
Speeding up Networks Mining via Neighborhood Diversity
Abstract
Parameterized complexity was classically used to efficiently solve NP-hard problems for small values of a fixed parameter. Then it has also been used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd) for several graph theoretic problems in P (e.g., Maximum Matching, Triangle counting and listing, Girth and Global minimum vertex cut). Such problems are known to admit algorithms parameterized by modular-width (mw) and consequently - being the nd a "special case" of mw - by nd. However, the proposed novel algorithms allow to improve the computational complexity from a time O(f(mw)⋅ n +m) - where n and m denote, respectively, the number of vertices and edges in the input graph - which is multiplicative in n to a time O(g(nd)+n +m) which is additive only in the size of the input.
Cite as
Gennaro Cordasco, Luisa Gargano, and Adele A. Rescigno. Speeding up Networks Mining via Neighborhood Diversity. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{cordasco_et_al:LIPIcs.FUN.2021.21,
author = {Cordasco, Gennaro and Gargano, Luisa and Rescigno, Adele A.},
title = {{Speeding up Networks Mining via Neighborhood Diversity}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {21:1--21:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.21},
URN = {urn:nbn:de:0030-drops-127823},
doi = {10.4230/LIPIcs.FUN.2021.21},
annote = {Keywords: Parameterized Complexity, Neighborhood Diversity, Maximum Matching, Triangle Counting, Girth, Global minimum vertex cut}
}
Document
Physical Zero-Knowledge Proof for Numberlink
Abstract
Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.
Cite as
Suthee Ruangwises and Toshiya Itoh. Physical Zero-Knowledge Proof for Numberlink. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{ruangwises_et_al:LIPIcs.FUN.2021.22,
author = {Ruangwises, Suthee and Itoh, Toshiya},
title = {{Physical Zero-Knowledge Proof for Numberlink}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {22:1--22:11},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.22},
URN = {urn:nbn:de:0030-drops-127836},
doi = {10.4230/LIPIcs.FUN.2021.22},
annote = {Keywords: Zero-knowledge proof, Card-based cryptography, Numberlink, Puzzles, Games}
}
Document
The Computational Complexity of Evil Hangman
Abstract
The game of Hangman is a classical asymmetric two player game in which one player, the setter, chooses a secret word from a language, that the other player, the guesser, tries to discover through single letter matching queries, answered by all occurrences of this letter if any. In the Evil Hangman variant, the setter can change the secret word during the game, as long as the new choice is consistent with the information already given to the guesser. We show that a greedy strategy for Evil Hangman can perform arbitrarily far from optimal, and most importantly, that playing optimally as an Evil Hangman setter is computationally difficult. The latter result holds even assuming perfect knowledge of the language, for several classes of languages, ranging from Finite to Turing Computable. The proofs are based on reductions to Dominating Set on 3-regular graphs and to the Membership problem, combinatorial problems already known to be computationally hard.
Cite as
Jérémy Barbay and Bernardo Subercaseaux. The Computational Complexity of Evil Hangman. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 23:1-23:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{barbay_et_al:LIPIcs.FUN.2021.23,
author = {Barbay, J\'{e}r\'{e}my and Subercaseaux, Bernardo},
title = {{The Computational Complexity of Evil Hangman}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {23:1--23:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.23},
URN = {urn:nbn:de:0030-drops-127840},
doi = {10.4230/LIPIcs.FUN.2021.23},
annote = {Keywords: combinatorial game theory, computational complexity, decidability, hangman}
}
Document
Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds
Abstract
Backoff algorithms are used in many distributed systems where multiple devices contend for a shared resource. For the classic balls-into-bins problem, the number of singletons - those bins with a single ball - is important to the analysis of several backoff algorithms; however, existing analyses employ advanced probabilistic tools to obtain concentration bounds. Here, we show that standard Chernoff bounds can be used instead, and the simplicity of this approach is illustrated by re-analyzing some well-known backoff algorithms.
Cite as
Qian M. Zhou, Aiden Calvert, and Maxwell Young. Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 24:1-24:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
Copy BibTex To Clipboard
@InProceedings{zhou_et_al:LIPIcs.FUN.2021.24,
author = {Zhou, Qian M. and Calvert, Aiden and Young, Maxwell},
title = {{Singletons for Simpletons: Revisiting Windowed Backoff with Chernoff Bounds}},
booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)},
pages = {24:1--24:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-145-0},
ISSN = {1868-8969},
year = {2020},
volume = {157},
editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.24},
URN = {urn:nbn:de:0030-drops-127859},
doi = {10.4230/LIPIcs.FUN.2021.24},
annote = {Keywords: Chernoff bounds, backoff, contention resolution, algorithms}
}