Found 2 Possible Name Variants:

Document

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

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.

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.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

**Published in:** Dagstuhl Reports, Volume 8, Issue 7 (2019)

From the 8th of July 2018 to the 13th of July 2018, a Dagstuhl Seminar took place with the topic "Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices".
There, 40 participants from as many as 14 distinct countries
and four distinct research areas, dealing with running time analysis and space usage analysis of algorithms and data structures, gathered to discuss results and techniques to "go beyond the worst-case" for classes of structurally restricted inputs, both for (fast) algorithms and (compressed) data structures.
The seminar consisted of (1) a first session of personal introduction, each participant presenting his expertise and themes of interests in two slides; (2) a series of four technical talks; and (3) a larger series of presentations of open problems, with ample time left for the participants to gather and work on such open problems.

Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{barbay_et_al:DagRep.8.7.44, author = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, title = {{Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)}}, pages = {44--61}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {8}, number = {7}, editor = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.7.44}, URN = {urn:nbn:de:0030-drops-101724}, doi = {10.4230/DagRep.8.7.44}, annote = {Keywords: adaptive (analysis of) algorithms, compressed data structures, compressed indices, parameterized complexity} }

Document

**Published in:** LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.

Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.CPM.2017.31, author = {Barbay, J\'{e}r\'{e}my and Ochoa, Carlos and Satti, Srinivasa Rao}, title = {{Synergistic Solutions on MultiSets}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.31}, URN = {urn:nbn:de:0030-drops-73441}, doi = {10.4230/LIPIcs.CPM.2017.31}, annote = {Keywords: deferred data structure, multivariate analysis, quick sort, select} }

Document

**Published in:** LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in less time than required to sort them on many large classes of instances, identified by a new measure of difficulty for this problem, the alternation alpha. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of fixed size n and alternation alpha. Such results refine the state of the art complexity in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort multisets (known since 1988).

Jérémy Barbay. Optimal Prefix Free Codes with Partial Sorting. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barbay:LIPIcs.CPM.2016.29, author = {Barbay, J\'{e}r\'{e}my}, title = {{Optimal Prefix Free Codes with Partial Sorting}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.29}, URN = {urn:nbn:de:0030-drops-60635}, doi = {10.4230/LIPIcs.CPM.2016.29}, annote = {Keywords: Deferred Data Structure, Huffman, Median, Optimal Prefix Free Codes, van Leeuwen.} }

Document

**Published in:** LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

The Hanoi Tower problem is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound correspond to the solution of a simple recursive function (the solution is so simple that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some minor change in the rules of the Hanoi Tower yields various increases of difficulty in the solution, so that to require a deeper mastery of recursion than the classical Hanoi Tower problem. In particular, we analyze the Selenite Tower problem, where just changing the insertion and extraction positions from the top to the middle of the tower results in a surprising increase in the intricacy of the solution: such a tower of n disks can be optimally moved in 3^(n/2) moves for n even (i.e. less than a Hanoi Tower of same height), via 5 recursive functions (or, equivalently, one recursion function with five states following three distinct patterns).

Jérémy Barbay. Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barbay:LIPIcs.FUN.2016.5, author = {Barbay, J\'{e}r\'{e}my}, title = {{Selenite Towers Move Faster Than Hano\"{i} Towers, But Still Require Exponential Time}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.5}, URN = {urn:nbn:de:0030-drops-58729}, doi = {10.4230/LIPIcs.FUN.2016.5}, annote = {Keywords: Br\"{a}hma tower, Disk Pile, Hanoi Tower, Levitating Tower, Recursivity} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

From 19.01. to 24.04.2009, the Dagstuhl Seminar
09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.1, author = {Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf}, title = {{09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.1}, URN = {urn:nbn:de:0030-drops-21228}, doi = {10.4230/DagSemProc.09171.1}, annote = {Keywords: Adaptive analysis, instance optimal algoritms, fixed parameter tractable, output sensitive algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Traditionally the analysis of algorithms measures the complexity of a
problem or algorithm in terms of the worst-case behavior over all
inputs of a given size. However, in certain cases an improved
algorithm can be obtained by considering a finer partition of the
input space. As this idea has been independently rediscovered in many areas, the
workshop gathered participants from different fields in order to
explore the impact and the limits of this technique, in the hope to
spring new collaboration and to seed the unification of the technique.

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.2, author = {Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf}, title = {{09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--1}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.2}, URN = {urn:nbn:de:0030-drops-21207}, doi = {10.4230/DagSemProc.09171.2}, annote = {Keywords: Adaptive analysis, instance optimal algorithms, fixed parameter tractable, output sensitive algorithms} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

We explore various techniques to compress a permutation $\pi$ over $n$ integers, taking advantage of ordered subsequences in $\pi$, while supporting its application $\pi(i)$ and the application of its inverse $\pi^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications $\pi^{k}(i)$ of it, of integer functions, and of inverted lists and suffix arrays.

Jeremy Barbay and Gonzalo Navarro. Compressed Representations of Permutations, and Applications. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 111-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.STACS.2009.1814, author = {Barbay, Jeremy and Navarro, Gonzalo}, title = {{Compressed Representations of Permutations, and Applications}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {111--122}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1814}, URN = {urn:nbn:de:0030-drops-18148}, doi = {10.4230/LIPIcs.STACS.2009.1814}, annote = {Keywords: Compression, Permutations, Succinct data structures, Adaptive sorting} }

Document

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

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.

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.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

**Published in:** Dagstuhl Reports, Volume 8, Issue 7 (2019)

From the 8th of July 2018 to the 13th of July 2018, a Dagstuhl Seminar took place with the topic "Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices".
There, 40 participants from as many as 14 distinct countries
and four distinct research areas, dealing with running time analysis and space usage analysis of algorithms and data structures, gathered to discuss results and techniques to "go beyond the worst-case" for classes of structurally restricted inputs, both for (fast) algorithms and (compressed) data structures.
The seminar consisted of (1) a first session of personal introduction, each participant presenting his expertise and themes of interests in two slides; (2) a series of four technical talks; and (3) a larger series of presentations of open problems, with ample time left for the participants to gather and work on such open problems.

Jérémy Barbay, Johannes Fischer, Stefan Kratsch, and Srinivasa Rao Satti. Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281). In Dagstuhl Reports, Volume 8, Issue 7, pp. 44-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{barbay_et_al:DagRep.8.7.44, author = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, title = {{Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)}}, pages = {44--61}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {8}, number = {7}, editor = {Barbay, J\'{e}r\'{e}my and Fischer, Johannes and Kratsch, Stefan and Satti, Srinivasa Rao}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.7.44}, URN = {urn:nbn:de:0030-drops-101724}, doi = {10.4230/DagRep.8.7.44}, annote = {Keywords: adaptive (analysis of) algorithms, compressed data structures, compressed indices, parameterized complexity} }

Document

**Published in:** LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum amount of work in the worst case over instances of size n and number of queries q fixed. Barbay et al. (2016) refined this approach to take advantage of the gaps between the positions hit by the queries (i.e., the structure in the queries). We develop new techniques in order to further refine this approach and take advantage all at once of the structure (i.e., the multiplicities of the elements), some notions of local order (i.e., the number and sizes of runs) and global order (i.e., the number and positions of existing pivots) in the input; and of the structure and order in the sequence of queries. Our main result is a synergistic deferred data structure which outperforms all solutions in the comparison model that take advantage of only a subset of these features. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of some notions of structure and order (local and global) in the input, improving upon previous results which take advantage only of the structure (Munro and Spira 1979) or of the local order (Takaoka 1997) in the input; and one new multiselection algorithm which takes advantage of not only the order and structure in the input, but also of the structure in the queries.

Jérémy Barbay, Carlos Ochoa, and Srinivasa Rao Satti. Synergistic Solutions on MultiSets. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.CPM.2017.31, author = {Barbay, J\'{e}r\'{e}my and Ochoa, Carlos and Satti, Srinivasa Rao}, title = {{Synergistic Solutions on MultiSets}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.31}, URN = {urn:nbn:de:0030-drops-73441}, doi = {10.4230/LIPIcs.CPM.2017.31}, annote = {Keywords: deferred data structure, multivariate analysis, quick sort, select} }

Document

**Published in:** LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in less time than required to sort them on many large classes of instances, identified by a new measure of difficulty for this problem, the alternation alpha. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of fixed size n and alternation alpha. Such results refine the state of the art complexity in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort multisets (known since 1988).

Jérémy Barbay. Optimal Prefix Free Codes with Partial Sorting. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barbay:LIPIcs.CPM.2016.29, author = {Barbay, J\'{e}r\'{e}my}, title = {{Optimal Prefix Free Codes with Partial Sorting}}, booktitle = {27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)}, pages = {29:1--29:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-012-5}, ISSN = {1868-8969}, year = {2016}, volume = {54}, editor = {Grossi, Roberto and Lewenstein, Moshe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.29}, URN = {urn:nbn:de:0030-drops-60635}, doi = {10.4230/LIPIcs.CPM.2016.29}, annote = {Keywords: Deferred Data Structure, Huffman, Median, Optimal Prefix Free Codes, van Leeuwen.} }

Document

**Published in:** LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

The Hanoi Tower problem is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound correspond to the solution of a simple recursive function (the solution is so simple that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some minor change in the rules of the Hanoi Tower yields various increases of difficulty in the solution, so that to require a deeper mastery of recursion than the classical Hanoi Tower problem. In particular, we analyze the Selenite Tower problem, where just changing the insertion and extraction positions from the top to the middle of the tower results in a surprising increase in the intricacy of the solution: such a tower of n disks can be optimally moved in 3^(n/2) moves for n even (i.e. less than a Hanoi Tower of same height), via 5 recursive functions (or, equivalently, one recursion function with five states following three distinct patterns).

Jérémy Barbay. Selenite Towers Move Faster Than Hanoï Towers, But Still Require Exponential Time. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{barbay:LIPIcs.FUN.2016.5, author = {Barbay, J\'{e}r\'{e}my}, title = {{Selenite Towers Move Faster Than Hano\"{i} Towers, But Still Require Exponential Time}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {5:1--5:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.5}, URN = {urn:nbn:de:0030-drops-58729}, doi = {10.4230/LIPIcs.FUN.2016.5}, annote = {Keywords: Br\"{a}hma tower, Disk Pile, Hanoi Tower, Levitating Tower, Recursivity} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

From 19.01. to 24.04.2009, the Dagstuhl Seminar
09171 ``Adaptive, Output Sensitive, Online and Parameterized Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.1, author = {Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf}, title = {{09171 Abstracts Collection – Adaptive, Output Sensitive, Online and Parameterized Algorithms}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.1}, URN = {urn:nbn:de:0030-drops-21228}, doi = {10.4230/DagSemProc.09171.1}, annote = {Keywords: Adaptive analysis, instance optimal algoritms, fixed parameter tractable, output sensitive algorithms} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009)

Traditionally the analysis of algorithms measures the complexity of a
problem or algorithm in terms of the worst-case behavior over all
inputs of a given size. However, in certain cases an improved
algorithm can be obtained by considering a finer partition of the
input space. As this idea has been independently rediscovered in many areas, the
workshop gathered participants from different fields in order to
explore the impact and the limits of this technique, in the hope to
spring new collaboration and to seed the unification of the technique.

Jérémy Barbay, Rolf Klein, Alejandro López-Ortiz, and Rolf Niedermeier. 09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms. In Adaptive, Output Sensitive, Online and Parameterized Algorithms. Dagstuhl Seminar Proceedings, Volume 9171, p. 1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:DagSemProc.09171.2, author = {Barbay, J\'{e}r\'{e}my and Klein, Rolf and L\'{o}pez-Ortiz, Alejandro and Niedermeier, Rolf}, title = {{09171 Executive Summary – Adaptive, Output Sensitive, Online and Parameterized Algorithms}}, booktitle = {Adaptive, Output Sensitive, Online and Parameterized Algorithms}, pages = {1--1}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9171}, editor = {J\'{e}r\'{e}my Barbay and Rolf Klein and Alejandro Ortiz-L\'{o}pez and Rolf Niedermeier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.2}, URN = {urn:nbn:de:0030-drops-21207}, doi = {10.4230/DagSemProc.09171.2}, annote = {Keywords: Adaptive analysis, instance optimal algorithms, fixed parameter tractable, output sensitive algorithms} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

We explore various techniques to compress a permutation $\pi$ over $n$ integers, taking advantage of ordered subsequences in $\pi$, while supporting its application $\pi(i)$ and the application of its inverse $\pi^{-1}(i)$ in small time. Our compression schemes yield several interesting byproducts, in many cases matching, improving or extending the best existing results on applications such as the encoding of a permutation in order to support iterated applications $\pi^{k}(i)$ of it, of integer functions, and of inverted lists and suffix arrays.

Jeremy Barbay and Gonzalo Navarro. Compressed Representations of Permutations, and Applications. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 111-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{barbay_et_al:LIPIcs.STACS.2009.1814, author = {Barbay, Jeremy and Navarro, Gonzalo}, title = {{Compressed Representations of Permutations, and Applications}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {111--122}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1814}, URN = {urn:nbn:de:0030-drops-18148}, doi = {10.4230/LIPIcs.STACS.2009.1814}, annote = {Keywords: Compression, Permutations, Succinct data structures, Adaptive sorting} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail