StringologyTimes

Data Structures and Algorithms: 2025/4/29-31

1: TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
2: Revisiting Directed Disjoint Paths on tournaments (and relatives)
3: Engineering Minimal k-Perfect Hash Functions
4: All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
5: List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
6: Approximately Dominating Sets in Elections
7: Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-Matrices
8: Warehouse storage and retrieval optimization via clustering, dynamic systems modeling, and GPU-accelerated routing
9: Deterministic Dynamic Maximal Matching in Sublinear Update Time
10: Approximate Lifted Model Construction
11: Effective Index Construction Algorithm for Optimal $(k,\eta)$-cores Computation
12: Online General Knapsack with Reservation Costs
13: Guessing Efficiently for Constrained Subspace Approximation
14: Provably faster randomized and quantum algorithms for $k$-means clustering via uniform sampling
15: Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model
16: The Metric Dimension of Sparse Random Graphs
17: Efficiently Finding All Minimal and Shortest Absent Subsequences in a String
18: Simulating quantum collision models with Hamiltonian simulations using early fault-tolerant quantum computers
19: Efficient Decomposition of Forman-Ricci Curvature on Vietoris-Rips Complexes and Data Applications
20: An $\mathcal{O}(n)$ Space Construction of Superpermutations