StringologyTimes

Data Structures and Algorithms: 2024/5/22-28

1: Approximating TSP Variants Using a Bridge Lemma
2: Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
3: Truncated Variance Reduced Value Iteration
4: Online Learning of Halfspaces with Massart Noise
5: Dequantizability from inputs
6: Average sensitivity of the Knapsack Problem
7: Quantum (Inspired) $D^2$-sampling with Applications
8: Faster Vizing and Near-Vizing Edge Coloring Algorithms
9: Recovering short generators via negative moments of Dirichlet $L$-functions
10: Cascading-Tree Algorithm for the 0-1 Knapsack Problem (In Memory of Heiner M{"u}ller-Merbach, a Former President of IFORS)
11: Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
12: Sparse Induced Subgraphs of Large Treewidth
13: On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
14: On connections between k-coloring and Euclidean k-means
15: Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint
16: Online Classification with Predictions
17: Deterministic Policies for Constrained Reinforcement Learning in Polynomial-Time
18: Graphlets correct for the topological information missed by random walks
19: Path-Reporting Distance Oracles with Linear Size
20: A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
21: Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
22: Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover
23: Efficient Certificates of Anti-Concentration Beyond Gaussians
24: Adaptive Dynamic Bitvectors
25: CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic Graphs
26: Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
27: Engineering Optimal Parallel Task Scheduling
28: When far is better: The Chamberlin-Courant approach to obnoxious committee selection
29: Faster $(\Delta + 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
30: Finding Induced Subgraphs from Graphs with Small Mim-Width
31: A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
32: Scaling up the Banded Matrix Factorization Mechanism for Differentially Private ML
33: Learning Minimum Linear Arrangement of Cliques and Lines
34: Hierarchical Clustering via Local Search
35: Boolean Matrix Multiplication for Highly Clustered Data on the Congested Clique
36: Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
37: Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
38: Finding Maximum Common Contractions Between Phylogenetic Networks
39: Delta-modular ILP Problems of Bounded Co-dimension, Discrepancy, and Convolution
40: Fully Subexponential Time Approximation Scheme for Product Partition
41: Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
42: Banana Trees for the Persistence in Time Series Experimentally
43: Graph Threading with Turn Costs
44: Tree Coloring: Random Order and Predictions
45: Avoiding Pitfalls for Privacy Accounting of Subsampled Mechanisms under Composition