StringologyTimes
STOC for Stringologist
STOC 2023
Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.
External Memory Fully Persistent Search Trees.
Weighted Edit Distance Computation: Strings, Trees, and Dyck.
Approximating Binary Longest Common Subsequence in Almost-Linear Time.
STOC 2022
Almost-optimal sublinear-time edit distance in the low distance regime.
Dynamic suffix array with polylogarithmic queries and updates.
Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios.
On the optimal time/space tradeoff for hash tables.
Explicit binary tree codes with sub-logarithmic size alphabet.
STOC 2021
Subcubic algorithms for Gomory-Hu tree in unweighted graphs.
Fully dynamic approximation of LIS in polylogarithmic time.
Improved dynamic algorithms for longest increasing subsequence.
STOC 2020
Approximating text-to-pattern Hamming distances.
Lower bound for succinct range minimum query.
Constant factor approximations to edit distance on far input pairs in nearly linear time.
Nearly optimal static Las Vegas succinct dictionary.
Constant-factor approximation of near-linear edit distance in near-linear time.
STOC 2019
Local decodability of the Burrows-Wheeler transform.
String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.
Optimal succinct rank data structure via approximate nonnegative tensor decomposition.
STOC 2018
Explicit binary tree codes with polylogarithmic size alphabet.
At the roots of dictionary compression: string attractors.
Smooth heaps and a dual view of self-adjusting data structures.
Synchronization strings: explicit constructions, local decoding, and applications.
STOC 2017
Synchronization strings: codes for insertions and deletions approaching the Singleton bound.
STOC 2016
Streaming algorithms for embedding and computing edit distance in the low distance regime.
STOC 2015
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).
STOC 2014
Linear time construction of compressed text indices in compact space.
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time.
STOC 2012
Strict fibonacci heaps.
Tight lower bounds for the online labeling problem.
STOC 2011
The power of simple tabulation hashing.
STOC 1999
Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems.
STOC 1997
On Sorting Strings in External Memory (Extended Abstract).
STOC 1987
Searching a Two Key Table Under a Single Key
STOC 1981
A Linear Probing Sort and its Analysis (Preliminary Draft)
STOC 1979
Implicit Data Structures (Preliminary Draft)
STOC 1977
The Analysis of an Improved Hashing Technique