StringologyTimes

FOCS for Stringologist

FOCS 2022

  1. Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract).
  2. Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
  3. Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.
  4. Online List Labeling: Breaking the log2n Barrier.
  5. Estimating the Longest Increasing Subsequence in Nearly Optimal Time.
  6. Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices.

FOCS 2021

  1. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance.
  2. Small-space and streaming pattern matching with $k$ edits.

FOCS 2020

  1. Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
  2. Faster Approximate Pattern Matching: A Unified Approach.
  3. On One-way Functions and Kolmogorov Complexity.
  4. Lazy Search Trees.
  5. Resolution of the Burrows-Wheeler Transform Conjecture.
  6. Edit Distance in Near-Linear Time: it’s a Constant Factor.

FOCS 2019

  1. Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
  2. Why are Proof Complexity Lower Bounds Hard?
  3. Sublinear Algorithms for Gap Edit Distance.
  4. Optimal Document Exchange and New Codes for Insertions and Deletions.
  5. Balancing Straight-Line Programs.

FOCS 2018

  1. Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.
  2. Bloom Filters, Adaptivity, and the Dictionary Problem.
  3. PanORAMa: Oblivious RAM with Logarithmic Overhead.

FOCS 2017

  1. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.

FOCS 2016

  1. Edit Distance: Sketching, Streaming, and Document Exchange.

FOCS 2015

  1. Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
  2. Pattern-Avoiding Access in Binary Search Trees.
  3. Tight Hardness Results for LCS and Other Sequence Similarity Measures.

FOCS 2014

  1. Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
  2. The Dyck Language Edit Distance Problem in Near-Linear Time.

FOCS 2012

  1. On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List.

FOCS 2010

  1. A Lower Bound for Dynamic Approximate Membership Data Structures.

FOCS 2005

  1. Structuring labeled trees for optimal succinctness, and beyond.

FOCS 2003

  1. Breaking a Time-and-Space Barrier in Constructing Full-Text Indices.

FOCS 2002

  1. Static Optimality Theorem for External Memory String Access.
  2. Implicit B-Trees: New Results for the Dictionary Problem.

FOCS 2000

  1. Opportunistic Data Structures with Applications.
  2. Cache-Oblivious B-Trees.

FOCS 1998

  1. Overcoming the Memory Bottleneck in Suffix Tree Construction.

FOCS 1997

  1. Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs.

FOCS 1990

  1. Permuting

FOCS 1985

  1. Robin Hood Hashing (Preliminary Report)

FOCS 1979

  1. Toward Self-Organizing Linear Search (Preliminary Draught)

FOCS 1978

  1. Selection and Sorting with Limited Storage

FOCS 1976

  1. Self-Organizing Binary Search Trees
This site is open source. Improve this page.