StringologyTimes

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

1: Diversity-Fair Online Selection
2: Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors
3: Learning with Positive and Imperfect Unlabeled Data
4: Balanced TSP partitioning
5: The Trie Measure, Revisited
6: Improved approximation algorithms for the EPR Hamiltonian
7: Robust Gittins for Stochastic Scheduling
8: An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
9: Tighter Bounds on Non-clairvoyant Parallel Machine Scheduling with Prediction to Minimize Makespan
10: BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs
11: Covering Approximate Shortest Paths with DAGs
12: Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time
13: Mildly-Interacting Fermionic Unitaries are Efficiently Learnable
14: Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
15: Optimal Hardness of Online Algorithms for Large Independent Sets
16: Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues
17: Enumeration of Bases in Matroid with Exponentially Large Ground Set
18: On the Problem of Best Arm Retention
19: Static to Dynamic Correlation Clustering
20: Kernels for Storage Capacity and Dual Index Coding
21: A Near-Optimal Kernel for a Coloring Problem
22: Fast Computation of the Discrete Fourier Transform Rectangular Index Coefficients
23: Quantum Search on Bipartite Multigraphs
24: Trading Prophets: How to Trade Multiple Stocks Optimally
25: Updating Lower and Upper Bounds for the Job-Shop Scheduling Problem Test Instances
26: Towards Optimal Distributed Edge Coloring with Small Palettes
27: A Bad Example for Jain’s Iterative Rounding Theorem for the Cover Small Cuts Problem
28: The Long Arm of Nashian Allocation in Online $p$-Mean Welfare Maximization
29: New Results on a General Class of Minimum Norm Optimization Problems
30: Broadcasting under Structural Restrictions
31: Robust Distributed Arrays: Provably Secure Networking for Data Availability Sampling
32: A New Impossibility Result for Online Bipartite Matching Problems
33: Temporal Graph Realization With Bounded Stretch
34: Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
35: Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
36: Approximate all-pairs Hamming distances and 0-1 matrix multiplication
37: The k-Center Problem of Uncertain Points on Graphs
38: Weakly Approximating Knapsack in Subquadratic Time
39: Explicit Lossless Vertex Expanders
40: Deterministic $k$-Median Clustering in Near-Optimal Time
41: Distribution Testing Meets Sum Estimation