3 Search Results for "Adler, Aviv"

Document
DOI: 10.4230/LIPIcs.FUN.2022.17
Skiing Is Easy, Gymnastics Is Hard: Complexity of Routine Construction in Olympic Sports

Authors: James Koppel and Yun William Yu

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

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-dev.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
DOI: 10.4230/LIPIcs.FUN.2021.1
Tatamibari Is NP-Complete

Authors: Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

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
DOI: 10.4230/LIPIcs.ICALP.2016.24
The Complexity of Hex and the Jordan Curve Theorem

Authors: Aviv Adler, Constantinos Daskalakis, and Erik D. Demaine

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
The Jordan curve theorem and Brouwer's fixed-point theorem are fundamental problems in topology. We study their computational relationship, showing that a stylized computational version of Jordan’s theorem is PPAD-complete, and therefore in a sense computationally equivalent to Brouwer’s theorem. As a corollary, our computational result implies that these two theorems directly imply each other mathematically, complementing Maehara's proof that Brouwer implies Jordan [Maehara, 1984]. We then turn to the combinatorial game of Hex which is related to Jordan's theorem, and where the existence of a winner can be used to show Brouwer's theorem [Gale,1979]. We establish that determining who won an (implicitly encoded) play of Hex is PSPACE-complete by adapting a reduction (due to Goldberg [Goldberg,2015]) from Quantified Boolean Formula (QBF). As this problem is analogous to evaluating the output of a canonical path-following algorithm for finding a Brouwer fixed point - and which is known to be PSPACE-complete [Goldberg/Papadimitriou/Savani, 2013] - we thereby establish a connection between Brouwer, Jordan and Hex higher in the complexity hierarchy.
Cite as

Aviv Adler, Constantinos Daskalakis, and Erik D. Demaine. The Complexity of Hex and the Jordan Curve Theorem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{adler_et_al:LIPIcs.ICALP.2016.24,
  author =	{Adler, Aviv and Daskalakis, Constantinos and Demaine, Erik D.},
  title =	{{The Complexity of Hex and the Jordan Curve Theorem}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.24},
  URN =		{urn:nbn:de:0030-drops-63032},
  doi =		{10.4230/LIPIcs.ICALP.2016.24},
  annote =	{Keywords: Jordan, Brouwer, Hex, PPAD, PSPACE}
}
  • Refine by Author
  • 2 Adler, Aviv
  • 2 Demaine, Erik D.
  • 1 Bosboom, Jeffrey
  • 1 Daskalakis, Constantinos
  • 1 Demaine, Martin L.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation

  • Refine by Keyword
  • 1 Brouwer
  • 1 Hex
  • 1 Jordan
  • 1 NP-hardness
  • 1 Nikoli puzzles
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2016
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact