StringologyTimes

Data Structures and Algorithms: 2023/9/15-21

1: Acceleration by Stepsize Hedging I: Multi-Step Descent and the Silver Stepsize Schedule
2: Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
3: On Induced Versions of Menger’s Theorem on Sparse Graphs
4: Fast Triangle Counting
5: Two-Sided Capacitated Submodular Maximization in Gig Platforms
6: Total Variation Distance Meets Probabilistic Inference
7: Concurrent Deterministic Skiplist and Other Data Structures
8: Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
9: A Tight Lower Bound of $\Omega(\log n)$ for the Estimation of the Number of Defective Items
10: Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
11: Sharp Phase Transition for Multi Overlap Gap Property in Ising $p$-Spin Glass and Random $k$-SAT Models
12: How to Make Knockout Tournaments More Popular?
13: A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning
14: Simple and Optimal Online Contention Resolution Schemes for $k$-Uniform Matroids
15: Graph Threading
16: Maintaining Matroid Intersections Online
17: A tight lower bound on non-adaptive group testing estimation
18: Online Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs
19: Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
20: K-Shortest Simple Paths Using Biobjective Path Search
21: Improved guarantees for the a priori TSP
22: Communication-Efficient Federated Learning via Regularized Sparse Random Networks
23: Improved bounds for the zeros of the chromatic polynomial via Whitney’s Broken Circuit Theorem
24: A Verified Cost Analysis of Joinable Red-Black Trees
25: Testing frequency distributions in a stream
26: Single-Exponential FPT Algorithms for Enumerating Secluded $\mathcal{F}$-Free Subgraphs and Deleting to Scattered Graph Classes
27: Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions
28: Temporal Network Core Decomposition and Community Search
29: BalCon – resource balancing algorithm for VM consolidation
30: Robust Approximation Algorithms for Non-monotone $k$-Submodular Maximization under a Knapsack Constraint
31: Simple Approximation Algorithms for Minimizing the Total Weighted Completion Time of Precedence-Constrained Jobs