StringologyTimes

STOC for Stringologist

STOC 2023

  1. Weighted Edit Distance Computation: Strings, Trees, and Dyck.
  2. External Memory Fully Persistent Search Trees.
  3. Locally Consistent Decomposition of Strings with Applications to Edit Distance Sketching.
  4. Approximating Binary Longest Common Subsequence in Almost-Linear Time.

STOC 2022

  1. On the optimal time/space tradeoff for hash tables.
  2. Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios.
  3. Almost-optimal sublinear-time edit distance in the low distance regime.
  4. Explicit binary tree codes with sub-logarithmic size alphabet.
  5. Dynamic suffix array with polylogarithmic queries and updates.

STOC 2021

  1. Fully dynamic approximation of LIS in polylogarithmic time.
  2. Subcubic algorithms for Gomory-Hu tree in unweighted graphs.
  3. Improved dynamic algorithms for longest increasing subsequence.

STOC 2020

  1. Constant factor approximations to edit distance on far input pairs in nearly linear time.
  2. Constant-factor approximation of near-linear edit distance in near-linear time.
  3. Nearly optimal static Las Vegas succinct dictionary.
  4. Lower bound for succinct range minimum query.
  5. Approximating text-to-pattern Hamming distances.

STOC 2019

  1. Optimal succinct rank data structure via approximate nonnegative tensor decomposition.
  2. Local decodability of the Burrows-Wheeler transform.
  3. String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure.

STOC 2018

  1. Smooth heaps and a dual view of self-adjusting data structures.
  2. Explicit binary tree codes with polylogarithmic size alphabet.
  3. Synchronization strings: explicit constructions, local decoding, and applications.
  4. At the roots of dictionary compression: string attractors.

STOC 2017

  1. Synchronization strings: codes for insertions and deletions approaching the Singleton bound.

STOC 2016

  1. Streaming algorithms for embedding and computing edit distance in the low distance regime.

STOC 2015

  1. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false).

STOC 2014

  1. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time.
  2. Linear time construction of compressed text indices in compact space.

STOC 2012

  1. Strict fibonacci heaps.
  2. Tight lower bounds for the online labeling problem.

STOC 2011

  1. The power of simple tabulation hashing.

STOC 1999

  1. Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems.

STOC 1997

  1. On Sorting Strings in External Memory (Extended Abstract).

STOC 1987

  1. Searching a Two Key Table Under a Single Key

STOC 1981

  1. A Linear Probing Sort and its Analysis (Preliminary Draft)

STOC 1979

  1. Implicit Data Structures (Preliminary Draft)

STOC 1977

  1. The Analysis of an Improved Hashing Technique
This site is open source. Improve this page.