StringologyTimes

STOC for Stringologist

STOC 2023

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

STOC 2022

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

STOC 2021

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

STOC 2020

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

STOC 2019

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

STOC 2018

  1. Explicit binary tree codes with polylogarithmic size alphabet.
  2. At the roots of dictionary compression: string attractors.
  3. Smooth heaps and a dual view of self-adjusting data structures.
  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. 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.