StringologyTimes

FOCS for Stringologist

FOCS 2022

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

FOCS 2021

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

FOCS 2020

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

FOCS 2019

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

FOCS 2018

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

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. The Dyck Language Edit Distance Problem in Near-Linear Time.
  2. Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.

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. Cache-Oblivious B-Trees.
  2. Opportunistic Data Structures with Applications.

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.