2 citations · 2 across the 4 of their papers we have counts for
4 papers
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka +1
Classically, the edit distance of two length- strings can be computed in time, whereas an -time procedure would falsify the Orthogonal Vectors Hypothesis. I…
Compressibility-Aware Quantum Algorithms on Strings
Daniel Gibney, Sharma V. Thankachan
Sublinear time quantum algorithms have been established for many fundamental problems on strings. This work demonstrates that new, faster quantum algorithms can be designed when th…
Optimal Encodings for Range Majority Queries
Gonzalo Navarro, Sharma V. Thankachan
We study the problem of designing a data structure that reports the positions of the distinct -majorities within any range of an array , without storing . A -major…
Fully Dynamic Data Structure for Top-k Queries on Uncertain Data
Manish Patil, Rahul Shah, Sharma V. Thankachan
Top- queries allow end-users to focus on the most important (top-) answers amongst those which satisfy the query. In traditional databases, a user defined score function assi…