StringologyTimes

Data Structures and Algorithms: 2021/7/15-21

1: Efficient Approximate Search for Sets of Vectors
2: Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More
3: Levenshtein Graphs: Resolvability, Automorphisms & Determining Sets
4: Online Allocation and Display Ads Optimization with Surplus Supply
5: On Optimal Approximations for $k$-Submodular Maximization via Multilinear Extension
6: An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes
7: Streaming Submodular Maximization under Matroid Constraints
8: Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
9: A Refined Approximation for Euclidean k-Means
10: Optimal Stopping Methodology for the Secretary Problem with Random Queries
11: Lossy Kernelization of Same-Size Clustering
12: Local Search for Weighted Tree Augmentation and Steiner Tree
13: Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update
14: Correlation detection in trees for planted graph alignment
15: Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
16: Streaming and Distributed Algorithms for Robust Column Subset Selection
17: Estimation from Partially Sampled Distributed Traces
18: Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fr'echet Distance
19: Skeletons and Minimum Energy Scheduling
20: On the Extended TSP Problem
21: On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
22: Single Pass Entrywise-Transformed Low Rank Approximation
23: DxHash: A Scalable Consistent Hash Based on the Pseudo-Random Sequence
24: Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
25: Learning Augmented Online Facility Location
26: Anti Tai Mapping for Unordered Labeled Trees
27: Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields
28: Efficient algorithms for maximum induced matching problem in permutation and trapezoid graphs
29: Computing the Fuzzy Partition Corresponding to the Greatest Fuzzy Auto-Bisimulation of a Fuzzy Graph-Based Structure
30: Sensitivity of string compressors and repetitiveness measures
31: Several methods of analysis for cardinality constrained bin packing
32: Algorithms for hard-constraint point processes via discretization
33: Hardness of Detecting Abelian and Additive Square Factors in Strings
34: Investigating the Recoverable Robust Single Machine Scheduling Problem Under Interval Uncertainty
35: CANITA: Faster Rates for Distributed Convex Optimization with Communication Compression
36: Learned Sorted Table Search and Static Indexes in Small Model Space
37: FPT Approximation for Fair Minimum-Load Clustering
38: Approximate Trace Reconstruction via Median String (in Average-Case)
39: Prime Factorization Using Quantum Variational Imaginary Time Evolution
40: Complexity of Source-Sink Monotone 2-Parameter Min Cut
41: Faster Matchings via Learned Duals
42: Non-existence of annular separators in geometric graphs
43: Optimizing the order of actions in contact tracing
44: On Reconfigurability of Target Sets
45: Decidability of Liveness on the TSO Memory Model
46: Optimal Rates for Nonparametric Density Estimation under Communication Constraints
47: Theory and Practice of Algorithm Engineering