StringologyTimes

STOC for Stringologist

STOC 2025

  1. On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM.

STOC 2023

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

STOC 2022

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

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

STOC 2019

  1. Local decodability of the Burrows-Wheeler transform.
  2. Optimal succinct rank data structure via approximate nonnegative tensor decomposition.
  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. At the roots of dictionary compression: string attractors.
  3. Explicit binary tree codes with polylogarithmic size alphabet.
  4. Synchronization strings: explicit constructions, local decoding, and applications.

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. Linear time construction of compressed text indices in compact space.
  2. Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time.

STOC 2012

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

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.