StringologyTimes

Data Structures and Algorithms: 2025/2/08-14

1: $O(\sqrt{T})$ Static Regret and Instance Dependent Constraint Violation for Constrained Online Convex Optimization
2: Exact Algorithms for Distance to Unique Vertex Cover
3: Computing and Learning on Combinatorial Data
4: A Randomised Approach to Distributed Sorting
5: Efficient distributional regression trees learning algorithms for calibrated non-parametric probabilistic forecasts
6: Algorithmic Problems in Categories of Partitions
7: Approximating the total variation distance between spin systems
8: New and Improved Bounds for Markov Paging
9: Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint
10: Combined Search and Encoding for Seeds, with an Application to Minimal Perfect Hashing
11: Near-Optimal Directed Low-Diameter Decompositions
12: Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
13: Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
14: Attainability of Two-Point Testing Rates for Finite-Sample Location Estimation
15: Sink-free orientations: a local sampler with applications
16: Faster Approximation Algorithms for k-Center via Data Reduction
17: Constant sensitivity on the CDAWGs
18: Amnesiac Flooding: Easy to break, hard to escape
19: Improved Sublinear Algorithms for Classical and Quantum Graph Coloring
20: Pcodec: Better Compression for Numerical Sequences
21: On the query complexity of sampling from non-log-concave distributions
22: Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
23: New simple and fast quicksort algorithm for equal keys
24: A Quadratic Lower Bound for Stable Roommates Solvability
25: ARRIVAL: Recursive Framework & $\ell_1$-Contraction
26: Approximation Algorithms for Optimal Hopsets
27: On the FirstFit Algorithm for Online Unit-Interval Coloring
28: Nearly Optimal Robust Covariance and Scatter Matrix Estimation Beyond Gaussians
29: Decay of correlation for edge colorings when $q>3\Delta$
30: Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices
31: Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
32: One-Shot Learning for k-SAT
33: Pareto Optimal Algorithmic Recourse in Multi-cost Function
34: Quantum Communication Advantage for Leader Election and Agreement
35: Exploring Word-Representable Temporal Graphs
36: Faster diameter computation in graphs of bounded Euler genus
37: Robust-Sorting and Applications to Ulam-Median
38: Private Low-Rank Approximation for Covariance Matrices, Dyson Brownian Motion, and Eigenvalue-Gap Bounds for Gaussian Perturbations
39: Coresets for Robust Clustering via Black-box Reductions to Vanilla Case
40: Online matching and market imbalance
41: Polynomial-Time Approximability of Constrained Reinforcement Learning
42: BalanceKV: KV Cache Compression through Discrepancy Theory
43: Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
44: Shortcuts and Transitive-Closure Spanners Approximation
45: Parallel $k$-Core Decomposition: Theory and Practice
46: Incremental Approximate Single-Source Shortest Paths with Predictions
47: Cost Preserving Dependent Rounding for Allocation Problems
48: Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
49: Model-Free Counterfactual Subset Selection at Scale
50: The Planted Spanning Tree Problem
51: Stable Hypergraph Matching in Unimodular Hypergraphs
52: Scalable Private Partition Selection via Adaptive Weighting
53: Linear-Time User-Level DP-SCO via Robust Statistics
54: Incremental Approximate Maximum Flow via Residual Graph Sparsification
55: Data Structures for Finite Downsets of Natural Vectors: Theory and Practice
56: Space-Efficient Quantum Error Reduction without log Factors
57: Moving Matter: Efficient Reconfiguration of Tile Arrangements by a Single Active Robot
58: A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
59: Deterministic Independent Sets in the Semi-Streaming Model
60: Forward-backward Contention Resolution Schemes for Fair Rationing
61: Robust Learning of Multi-index Models via Iterative Subspace Approximation
62: Fast Tensor Completion via Approximate Richardson Iteration
63: Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs
64: Optimal $k$-Secretary with Logarithmic Memory