StringologyTimes

SODA for Stringologist

SODA 2023

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

SODA 2022

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

SODA 2021

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

SODA 2020

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

SODA 2019

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

SODA 2018

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

SODA 2017

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

SODA 2016

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

SODA 2015

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

SODA 2014

  1. Finding small patterns in permutations in linear time.
  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. Bicriteria data compression.

SODA 2013

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

SODA 2012

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

SODA 2011

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

SODA 2010

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

SODA 2009

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