StringologyTimes

Data Structures and Algorithms: 2025/5/15-21

1: An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale
2: High-Temperature Fermionic Gibbs States are Mixtures of Gaussian States
3: $XX^{t}$ Can Be Faster
4: Improved Rank Aggregation under Fairness Constraint
5: Price of Anarchy for Congestion and Scheduling Games via Vector Fitting
6: Simpler and Faster Directed Low-Diameter Decompositions
7: Generalization of Repetitiveness Measures for Two-Dimensional Strings
8: Prefix-bounded matrices
9: Bandwidth vs BFS Width in Matrix Reordering, Graph Reconstruction, and Graph Drawing
10: Lasso and Partially-Rotated Designs
11: Locally Differentially Private Graph Clustering via the Power Iteration Method
12: Symbolic Model Checking in External Memory
13: Depth first representations of $k^2$-trees
14: Computing in a Faulty Congested Clique
15: Unsolvability and Beyond in Many-To-Many Non-Bipartite Stable Matching
16: Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
17: XiSort: Deterministic Sorting via IEEE-754 Total Ordering and Entropy Minimization
18: A Reduction-based Algorithm for the Clique Interdiction Problem
19: Logarithmic Approximations for Fair k-Set Selection
20: Fair Submodular Maximization over a Knapsack Constraint
21: BOLT: Block-Orthonormal Lanczos for Trace estimation of matrix functions
22: ResidualSketch: Enhancing Layer Efficiency and Error Reduction in Hierarchical Heavy Hitter Detection with ResNet Innovations
23: Nonlinear Laplacians: Tunable principal component analysis under directional prior information
24: Private Statistical Estimation via Truncation
25: Fast and Simple Densest Subgraph with Predictions
26: More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
27: Counting Graphlets of Size $k$ under Local Differential Privacy
28: A Faster Parametric Search for the Integral Quickest Transshipment Problem
29: New Sorting Algorithm Wave Sort (W-Sort)
30: Unsplittable Multicommodity Flows in Outerplanar Graphs
31: Differentially Private Quantiles with Smaller Error
32: ResQue Greedy: Rewiring Sequential Greedy for Improved Submodular Maximization
33: Robust learning of halfspaces under log-concave marginals
34: Path Contraction Faster than $2^n$
35: A Single Exponential-Time FPT Algorithm for Cactus Contraction
36: Exploring Temporal Graphs with Frequent and Regular Edges
37: Linear Hashing Is Optimal
38: Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
39: A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Input
40: Credible Sets of Phylogenetic Tree Topology Distributions
41: Approximate Spanning Tree Counting from Uncorrelated Edge Sets
42: Optimizing Age-of-Information in Piggyback Networks with Recurrent Data Generation
43: Parallel Scan on Ascend AI Accelerators
44: Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
45: Group Order Logic
46: A Faster Algorithm for Independent Cut