StringologyTimes

Data Structures and Algorithms: 2022/10/15-21

1: Popularity on the Roommate Diversity Problem
2: Faster Space-Efficient STR-IC-LCS Computation
3: Gibbs Sampling of Periodic Potentials on a Quantum Computer
4: Performance evaluation of approximation algorithms for the minimum size 2-vertex strongly connected subgraph problem
5: A Nearly Optimal Size Coreset Algorithm with Nearly Linear Time
6: Minimizing low-rank models of high-order tensors: Hardness, span, tight relaxation, and applications
7: A Note on Quantum Divide and Conquer for Minimal String Rotation
8: Clustering Categorical Data: Soft Rounding k-modes
9: Capacitated Vehicle Routing in Graphic Metrics
10: First Order Logic on Pathwidth Revisited Again
11: Computing MEMs and Relatives on Repetitive Text Collections
12: Towards Practical Explainability with Cluster Descriptors
13: SQ Lower Bounds for Learning Single Neurons with Massart Noise
14: Optimized Telecloning Circuits: Theory and Practice of Nine NISQ Clones
15: Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
16: Faster Matrix Multiplication via Asymmetric Hashing
17: On Hitting Times for General Quantum Markov Processes
18: On the Perturbation Function of Ranking and Balance for Weighted Online Bipartite Matching
19: Near-optimal Coresets for Robust Clustering
20: Dense subgraphs induced by edge labels
21: A Polynomial-time Algorithm for the Large Scale of Airplane Refueling Problem
22: List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
23: Substring Density Estimation from Traces
24: Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
25: A general model-and-run solver for multistage robust discrete linear optimization
26: Cutting-plane algorithms for preemptive uniprocessor real-time scheduling problems
27: Noisy Tree Data Structures and Quantum Applications
28: Learning-Augmented Private Algorithms for Multiple Quantile Release
29: Block subsampled randomized Hadamard transform for low-rank approximation on distributed architectures
30: Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenance
31: Online Matching with Cancellation Costs
32: Two-stage Stochastic Matching and Pricing with Applications to Ride Hailing
33: Rerouting Planar Curves and Disjoint Paths
34: A Simple Deterministic Distributed Low-Diameter Clustering
35: Solving the Probabilistic Profitable Tour Problem on a Tree
36: Splay Top Trees
37: Efficient Submodular Optimization under Noise: Local Search is Robust
38: Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries