143 citations · 479 across the 107 of their papers we have counts for
5 papers · 1 filter
Bounds from a Card Trick
Travis Gagie
We describe a new variation of a mathematical card trick, whose analysis leads to new lower bounds for data compression and estimating the entropy of Markov sources.
New Algorithms on Wavelet Trees and Applications to Information Retrieval
Travis Gagie, Gonzalo Navarro, Simon J. Puglisi
Wavelet trees are widely used in the representation of sequences, permutations, text collections, binary relations, discrete points, and other succinct data structures. We show, ho…
Counting Colours in Compressed Strings
Travis Gagie, Juha Kärkkäinen
Suppose we are asked to preprocess a string \(s [1..n]\) such that later, given a substring's endpoints, we can quickly count how many distinct characters it contains. In this pape…
Pattern Kits
Travis Gagie, Kalle Karhu, Juha Kärkkäinen +2
Suppose we have just performed searches in a self-index for two patterns and and now we want to search for their concatenation \A B); how can we best make use of our previo…
Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case
Ferdinando Cicalese, Travis Gagie, Eduardo Laber +1
We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not inclu…