StringologyTimes

SODA for Stringologist

SODA 2023

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

SODA 2022

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

SODA 2021

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

SODA 2020

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

SODA 2019

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

SODA 2018

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

SODA 2017

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

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

SODA 2014

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

SODA 2013

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

SODA 2012

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

SODA 2011

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

SODA 2010

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