7 citations · 15 across the 20 of their papers we have counts for
24 papers
Fun Maximizing Search, (Non) Instance Optimality, and Video Games for Parrots
Jérémy Barbay
Computerized Adaptive Testing (CAT) measures an examinee's ability while adapting to their level. Both too many questions and too many hard questions can make a test frustrating. A…
Measuring Discrimination Abilities of Monk Parakeets Between Discreet and Continuous Quantities Through a Digital Life Enrichment Application
Jérémy Barbay, Fabián Jaña, Cristóbal Sepulveda Álvarez
Ain et al. measured three African Grey (Psittacus erithacus) parrot's discrimination abilities between discreet and continuous quantities. Some features of their experimental proto…
The Computational Complexity of Evil Hangman
Jérémy Barbay, Bernardo Subercaseaux
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 d…
Indexed Dynamic Programming to boost Edit Distance and LCSS Computation
Jérémy Barbay, Andrés Olivares
There are efficient dynamic programming solutions to the computation of the Edit Distance from to , for many natural subsets of edit operations, typica…
Adaptive Computation of the Discrete Fréchet Distance
Jérémy Barbay
The discrete Fr{é}chet distance is a measure of similarity between point sequences which permits to abstract differences of resolution between the two curves, approximating the ori…
Computing Coverage Kernels Under Restricted Settings
Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma
We consider the Minimum Coverage Kernel problem: given a set of -dimensional boxes, find a subset of of minimum size covering the same region as . This problem is $\m…
Depth Distribution in High Dimensions
Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma
Motivated by the analysis of range queries in databases, we introduce the computation of the Depth Distribution of a set of axis aligned boxes, whose computation gene…
Synergistic Computation of Planar Maxima and Convex Hull
Jérémy Barbay, Carlos Ochoa
Refinements of the worst case complexity over instances of fixed input size consider the input order or the input structure, but rarely both at the same time. Barbay et al. [2016]…
Multivariate Analysis for Computing Maxima in High Dimensions
Jérémy Barbay, Javiel Rojas
We study the problem of computing the \textsc{Maxima} of a set of -dimensional points. For dimensions 2 and 3, there are algorithms to solve the problem with order-oblivious…
Synergistic Sorting, MultiSelection and Deferred Data Structures on MultiSets
Jérémy Barbay, Carlos Ochoa, Srinivasa Rao Satti
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…
Bouncing Towers move faster than Hanoi Towers, but still require exponential time
Jérémy Barbay
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 t…
Optimal Prefix Free Codes With Partial Sorting
Jérémy Barbay
We describe an algorithm computing an optimal prefix free code for unsorted positive weights in time within , where the alternation $α\in[1..n…
Adaptive Computation of the Klee's Measure in High Dimensions
Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma
The KLEE'S MESURE of axis-parallel boxes in is the volume of their union. It can be computed in time within in the worst case. We describe three tec…
Refining the Analysis of Divide and Conquer: How and When
Jeremy Barbay, Carlos Ochoa, Pablo Perez-Lantero
Divide-and-conquer is a central paradigm for the design of algorithms, through which some fundamental computational problems, such as sorting arrays and computing convex hulls, are…
Instance Optimal Geometric Algorithms
Peyman Afshani, Jérémy Barbay, Timothy Chan
We prove the existence of an algorithm for computing 2-d or 3-d convex hulls that is optimal for every point set in the following sense: for every sequence of points an…
Adaptive Computation of the Swap-Insert Correction Distance
Jérémy Barbay, Pablo Pérez-Lantero
The Swap-Insert Correction distance from a string of length to another string of length on the alphabet is the minimum number of insertions, and swap…
Near-Optimal Online Multiselection in Internal and External Memory
Jérémy Barbay, Ankur Gupta, S. Srinivasa Rao +1
We introduce an online version of the multiselection problem, in which q selection queries are requested on an unsorted array of n elements. We provide the first online algorithm t…
Adaptive Techniques to find Optimal Planar Boxes
J. Barbay, G. Navarro, P. Pérez-Lantero
Given a set of planar points, two axes and a real-valued score function on subsets of , the Optimal Planar Box problem consists in finding a box (i.e. axis-aligned…
Optimal Prefix Free Code in Linear Time
Jérémy Barbay
We describe an algorithm computing an optimal prefix free code from unsorted positive integer weights in time linear in the number of machine words holding those weights. This…
Compact Binary Relation Representations with Rich Functionality
Jérémy Barbay, Francisco Claude, Gonzalo Navarro
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 operation…
On Compressing Permutations and Adaptive Sorting
Jérémy Barbay, Gonzalo Navarro
Previous compact representations of permutations have focused on adding a small index on top of the plain data , in order to efficiently support the applicati…
LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
Jérémy Barbay, Johannes Fischer
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 prev…
Efficient Fully-Compressed Sequence Representations
Jeremy Barbay, Francisco Claude, Travis Gagie +2
We present a data structure that stores a sequence over alphabet in $n\Ho(s) + o(n)(\Ho(s){+}1)$ bits, where $\Ho(s)$ is the zero-order entropy of . This stru…
Compressed Representations of Permutations, and Applications
Jérémy Barbay, Gonzalo Navarro
We explore various techniques to compress a permutation over n integers, taking advantage of ordered subsequences in , while supporting its application (i) and the applic…