StringologyTimes

SODA for Stringologist

SODA 2023

  1. A Tight Analysis of Slim Heaps and Smooth Heaps.
  2. Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance.
  3. Tiny Pointers.
  4. Breaking the 𝒪(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees.
  5. A Nearly-Tight Analysis of Multipass Pairing Heaps.
  6. Tight Bounds for Monotone Minimal Perfect Hashing.
  7. Optimal Square Detection Over General Alphabets.
  8. 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time.
  9. Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching.
  10. Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures.

SODA 2022

  1. How many Clusters? - An algorithmic answer.
  2. Pattern Matching on Grammar-Compressed Strings in Linear Time.
  3. Splay trees on trees.
  4. Simulating a stack using queues.
  5. An Improved Algorithm for The k-Dyck Edit Distance Problem.
  6. How Compression and Approximation Affect Efficiency in String Distance Measures.
  7. Enumerating k-SAT functions.
  8. A Lower Bound for the n-queens Problem.
  9. Selectable Heaps and Optimal Lazy Search Trees.
  10. Streaming Regular Expression Membership and Pattern Matching.
  11. An Upper Bound and Linear-Space Queries on the LZ-End Parsing.
  12. Average Sensitivity of Dynamic Programming.

SODA 2021

  1. On Indexing and Compressing Finite Automata.
  2. A Lower Bound for Dynamic Fractional Cascading.
  3. Optimal Oblivious Priority Queues.
  4. Beating the probabilistic lower bound on perfect hashing.
  5. On Locating Paths in Compressed Tries.
  6. Competitive Data-Structure Dynamization.
  7. New Data Structures for Orthogonal Range Reporting and Range Minima Queries.

SODA 2020

  1. Regular Languages meet Prefix Sorting.
  2. Reducing approximate Longest Common Subsequence to approximate Edit Distance.
  3. Combinatorial generation via permutation languages.
  4. Better Data Structures for Colored Orthogonal Range Reporting.
  5. Improved Algorithms for Edit Distance and LCS: Beyond Worst Case.
  6. A Lower Bound for Jumbled Indexing.
  7. Locally Consistent Parsing for Text Indexing in Small Space.
  8. Competitive Online Search Trees on Trees.

SODA 2019

  1. Lower Bounds for Oblivious Data Structures.
  2. Optimal Construction of Compressed Indexes for Highly Repetitive Texts.
  3. Synchronization Strings: Highly Efficient Deterministic Constructions over Small Alphabets.
  4. List Decoding with Double Samplers.
  5. The streaming k-mismatch problem.
  6. Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts.
  7. Efficiently Approximating Edit Distance Between Pseudorandom Strings.
  8. Lower bounds for text indexing with mismatches and differences.

SODA 2018

  1. Optimal-Time Text Indexing in BWT-runs Bounded Space.
  2. The Entropy of Backwards Analysis.
  3. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can).
  4. Improved bounds for testing Dyck languages.
  5. Optimal Dynamic Strings.
  6. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy.
  7. Multivariate Fine-Grained Complexity of Longest Common Subsequence.
  8. In-Place Sparse Suffix Sorting.
  9. Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees.
  10. Time and Space Efficient Representations of Distributive Lattices.

SODA 2017

  1. Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time.
  2. Hardness of Permutation Pattern Matching.
  3. Sparse Suffix Tree Construction in Optimal Time and Space.
  4. pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems.
  5. File Maintenance: When in Doubt, Change the Layout!

SODA 2016

  1. The k-mismatch problem revisited.
  2. Weighted dynamic finger in binary search trees.
  3. Range Predecessor and Lempel-Ziv Parsing.

SODA 2015

  1. Approximate Range Emptiness in Constant Time and Optimal Space.
  2. Internal Pattern Matching Queries in a Text and Applications.
  3. Wavelet Trees Meet Suffix Trees.
  4. A new characterization of maximal repetitions by Lyndon trees.
  5. The amortized cost of finding the minimum.
  6. Cell-probe bounds for online edit distance and other pattern matching problems.

SODA 2014

  1. Bicriteria data compression.
  2. Concurrent Range Reporting in Two-Dimensional Space.
  3. Near-optimal labeling schemes for nearest common ancestors.
  4. Selection and Sorting in the “Restore” Model.
  5. Finding small patterns in permutations in linear time.

SODA 2013

  1. Optimal Dynamic Sequence Representations.
  2. Compressed static functions with applications.
  3. Lyndon Words and Short Superstrings.
  4. Twisted Tabulation Hashing.
  5. The Space Complexity of 2-Dimensional Approximate Range Counting.
  6. Near-Optimal Range Reporting Structures for Categorical Data.
  7. Adaptive and Approximate Orthogonal Range Counting.

SODA 2012

  1. Using hashing to solve the dictionary problem.
  2. I/O-efficient data structures for colored range and prefix reporting.
  3. Top-k document retrieval in optimal time and linear space.
  4. Fully persistent B-trees.
  5. A linear time algorithm for seeds computation.

SODA 2011

  1. Optimal pattern matching in LZW compressed strings.
  2. Persistent Predecessor Search and Orthogonal point Location on the Word RAM.
  3. Random Access to grammar-Compressed Strings.
  4. Improved Space Bounds for Cache-Oblivious Range Reporting.
  5. Ordered and Unordered Top-K Range Reporting in Large Data Sets.
  6. Top-K Color Queries for Document Retrieval.

SODA 2010

  1. Data Structures for Range Minimum Queries in Multidimensional Arrays.
  2. Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities.
  3. Randomized Shellsort: A Simple Oblivious Sorting Algorithm.
  4. Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs.
  5. Deletion Without Rebalancing in Balanced Binary Trees.
  6. Data-Specific Analysis of String Sorting.
  7. Counting Inversions, Offline Orthogonal Range Counting, and Related Problems.
  8. On the Cell Probe Complexity of Dynamic Membership.
  9. Cell-Probe Lower Bounds for Succinct Partial Sums.
  10. Fully-Functional Succinct Trees.
  11. Regular Expression Matching with Multi-Strings and Intervals.

SODA 2009

  1. Monotone minimal perfect hashing: searching a sorted table with O(1) accesses.
This site is open source. Improve this page.