StringologyTimes
FOCS for Stringologist
FOCS 2022
Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices.
Estimating the Longest Increasing Subsequence in Nearly Optimal Time.
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal.
Online List Labeling: Breaking the log2n Barrier.
Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract).
Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance.
FOCS 2021
Small-space and streaming pattern matching with $k$ edits.
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance.
FOCS 2020
Faster Approximate Pattern Matching: A Unified Approach.
Edit Distance in Near-Linear Time: it’s a Constant Factor.
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance.
Resolution of the Burrows-Wheeler Transform Conjecture.
Lazy Search Trees.
On One-way Functions and Kolmogorov Complexity.
FOCS 2019
Approximation Algorithms for LCS and LIS with Truly Improved Running Times.
Balancing Straight-Line Programs.
Why are Proof Complexity Lower Bounds Hard?
Optimal Document Exchange and New Codes for Insertions and Deletions.
Sublinear Algorithms for Gap Edit Distance.
FOCS 2018
PanORAMa: Oblivious RAM with Logarithmic Overhead.
Bloom Filters, Adaptivity, and the Dictionary Problem.
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time.
FOCS 2017
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve.
FOCS 2016
Edit Distance: Sketching, Streaming, and Document Exchange.
FOCS 2015
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping.
Pattern-Avoiding Access in Binary Search Trees.
Tight Hardness Results for LCS and Other Sequence Similarity Measures.
FOCS 2014
The Dyck Language Edit Distance Problem in Near-Linear Time.
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search.
FOCS 2012
On-Line Indexing for General Alphabets via Predecessor Queries on Subsets of an Ordered List.
FOCS 2010
A Lower Bound for Dynamic Approximate Membership Data Structures.
FOCS 2005
Structuring labeled trees for optimal succinctness, and beyond.
FOCS 2003
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices.
FOCS 2002
Static Optimality Theorem for External Memory String Access.
Implicit B-Trees: New Results for the Dictionary Problem.
FOCS 2000
Cache-Oblivious B-Trees.
Opportunistic Data Structures with Applications.
FOCS 1998
Overcoming the Memory Bottleneck in Suffix Tree Construction.
FOCS 1997
Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs.
FOCS 1990
Permuting
FOCS 1985
Robin Hood Hashing (Preliminary Report)
FOCS 1979
Toward Self-Organizing Linear Search (Preliminary Draught)
FOCS 1978
Selection and Sorting with Limited Storage
FOCS 1976
Self-Organizing Binary Search Trees