BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Jérémy Barbay

Jérémy Barbay appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputational ComplexityComputational GeometryGeneral LiteratureOther Computer Science

Catalog footprint

What is connected

11works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

Measuring Discrimination Abilities of Monk Parakeets Between Discreet and Continuous Quantities Through a Digital Life Enrichment Application

Ain et al. measured three African Grey (Psittacus erithacus) parrot's discrimination abilities between discreet and continuous quantities. Some features of their experimental protocol make it difficult to apply to other subjects and/or species without introducing a risk for some bias, as subjects could read cues from the experimenter (even though the study's subjects probably did not). Can digital life enrichment techniques permit us to replicate their results with other species with less risk for experimental bias, with a better precision, and at lower cost? Inspired by previous informal digital life enrichment experiments with parrots, we designed and tested a web application to digitally replicate and extend Ain et al.'s experimental setup. We were able to obtain similar results to theirs for two individuals from a distinct species, Monk Parakeets (Myiopsitta Monachus), with increased guarantees against potential experimental biases, in a way which should allow to replicate such experiments at larger scale and at a much lower cost.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The Computational Complexity of Evil Hangman

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Bouncing Towers move faster than Hanoi Towers, but still require exponential time

The problem of the Hanoi Tower is a classic exercise in recursive programming: the solution has a simple recursive definition, and its complexity and the matching lower bound are the solution of a simple recursive function (the solution is so easy that most students memorize it and regurgitate it at exams without truly understanding it). We describe how some very minor changes in the rules of the Hanoi Tower yield various increases of complexity in the solution, so that they require a deeper analysis than the classical Hanoi Tower problem while still yielding exponential solutions. In particular, we analyze the problem fo the Bouncing Tower, where just changing the insertion and extraction position from the top to the middle of the tower results in a surprising increase of complexity in the solution: such a tower of $n$ disks can be optimally moved in $\sqrt{3}^n$ moves for $n$ even (i.e. less than a Hanoi Tower of same height), via $5$ recursive functions (or, equivalently, one recursion function with $5$ states).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Prefix Free Codes With Partial Sorting

We describe an algorithm computing an optimal prefix free code for $n$ unsorted positive weights in time within $O(n(1+\lg α))\subseteq O(n\lg n)$, where the alternation $α\in[1..n-1]$ measures the amount of sorting required by the computation. 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 size $n$ and alternation $α$. Such results refine the state of the art complexity of $Θ(n\lg n)$ 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 a multiset depending on the queries on it (known since 1988).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Synergistic Sorting, MultiSelection and Deferred Data Structures on MultiSets

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 (i.e., the query size). 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 to take advantage all at once of the structure (i.e., the multiplicities of the elements), the local order (i.e., the number and sizes of runs) and the 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 performs much better on large classes of instances, while performing always asymptotically as good as previous solutions. As intermediate results, we describe two new synergistic sorting algorithms, which take advantage of the 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. We described two compressed data structures to represent a multiset taking advantage of both the local order and structure, while supporting the operators rank and select on the multiset.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Adaptive Computation of the Klee's Measure in High Dimensions

The KLEE'S MESURE of $n$ axis-parallel boxes in $\mathbb{R}^d$ is the volume of their union. It can be computed in time within $O(n^{d/2})$ in the worst case. We describe three techniques to boost its computation: one based on some type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of the structure of the input. The first technique benefits from instances where the MAXIMA of the input is of small size $h$, and yields a solution running in time within $O(n\log^{2d-2}{h}+ h^{d/2}) \subseteq O(n^{d/2}$). The second technique takes advantage of instances where no $d$-dimensional axis-aligned hyperplane intersects more than $k$ boxes in some dimension, and yields a solution running in time within $O(n \log n + n k^{(d-2)/2}) \subseteq O(n^{d/2})$. The third technique takes advantage of instances where the \emph{intersection graph} of the input has small treewidth $ω$. It yields an algorithm running in time within $O(n^4ω\log ω+ n (ω\log ω)^{d/2})$ in general, and in time within $O(n \log n + n ω^{d/2})$ if an optimal tree decomposition of the intersection graph is given. We show how to combine these techniques in an algorithm which takes advantage of all three configurations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Adaptive Computation of the Swap-Insert Correction Distance

The Swap-Insert Correction distance from a string $S$ of length $n$ to another string $L$ of length $m\geq n$ on the alphabet $[1..d]$ is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting $S$ into $L$. Contrarily to other correction distances, computing it is NP-Hard in the size $d$ of the alphabet. We describe an algorithm computing this distance in time within $O(d^2 nm g^{d-1})$, where there are $n_α$ occurrences of $α$ in $S$, $m_α$ occurrences of $α$ in $L$, and where $g=\max_{α\in[1..d]} \min\{n_α,m_α-n_α\}$ measures the difficulty of the instance. The difficulty $g$ is bounded by above by various terms, such as the length of the shortest string $S$, and by the maximum number of occurrences of a single character in $S$. Those results illustrate how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Instance Optimal Geometric Algorithms

We prove the existence of an algorithm $A$ for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every sequence $σ$ of $n$ points and for every algorithm $A'$ in a certain class $\mathcal{A}$, the running time of $A$ on input $σ$ is at most a constant factor times the maximum running time of $A'$ on the worst possible permutation of $σ$ for $A'$. We establish a stronger property: for every sequence $σ$ of points and every algorithm $A'$, the running time of $A$ on $σ$ is at most a constant factor times the average running time of $A'$ over all permutations of $σ$. We call algorithms satisfying these properties instance-optimal in the order-oblivious and random-order setting. Such instance-optimal algorithms simultaneously subsume output-sensitive algorithms and distribution-dependent average-case algorithms, and all algorithms that do not take advantage of the order of the input or that assume the input is given in a random order. The class $\mathcal{A}$ under consideration consists of all algorithms in a decision tree model where the tests involve only multilinear functions with a constant number of arguments. To establish an instance-specific lower bound, we deviate from traditional Ben-Or-style proofs and adopt a new adversary argument. For 2-d convex hulls, we prove that a version of the well known algorithm by Kirkpatrick and Seidel (1986) or Chan, Snoeyink, and Yap (1995) already attains this lower bound. For 3-d convex hulls, we propose a new algorithm. We further obtain instance-optimal results for a few other standard problems in computational geometry. Our framework also reveals connection to distribution-sensitive data structures and yields new results as a byproduct, for example, on on-line orthogonal range searching in 2-d and on-line halfspace range reporting in 2-d and 3-d.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Compact Binary Relation Representations with Rich Functionality

Binary relations are an important abstraction arising in many data representation problems. The data structures proposed so far to represent them support just a few basic operations required to fit one particular application. We identify many of those operations arising in applications and generalize them into a wide set of desirable queries for a binary relation representation. We also identify reductions among those operations. We then introduce several novel binary relation representations, some simple and some quite sophisticated, that not only are space-efficient but also efficiently support a large subset of the desired queries.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On Compressing Permutations and Adaptive Sorting

Previous compact representations of permutations have focused on adding a small index on top of the plain data $<π(1), π(2),...π(n)>$, in order to efficiently support the application of the inverse or the iterated permutation. In this paper we initiate the study of techniques that exploit the compressibility of the data itself, while retaining efficient computation of $π(i)$ and its inverse. In particular, we focus on exploiting {\em runs}, which are subsets (contiguous or not) of the domain where the permutation is monotonic. Several variants of those types of runs arise in real applications such as inverted indexes and suffix arrays. Furthermore, our improved results on compressed data structures for permutations also yield better adaptive sorting algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations

LRM-Trees are an elegant way to partition a sequence of values into sorted consecutive blocks, and to express the relative position of the first element of each block within a previous block. They were used to encode ordinal trees and to index integer arrays in order to support range minimum queries on them. We describe how they yield many other convenient results in a variety of areas, from data structures to algorithms: some compressed succinct indices for range minimum queries; a new adaptive sorting algorithm; and a compressed succinct data structure for permutations supporting direct and indirect application in time all the shortest as the permutation is compressible.

0 citations0 reviewsNo code linkedOpen access