StringologyTimes

Data Structures and Algorithms: 2024/7/15-21

1: Low Sensitivity Hopsets
2: Online Matroid Embeddings
3: The Average-Value Allocation Problem
4: 9/7-Approximation for Two-Edge-Connectivity and Two-Vertex-Connectivity
5: Spanning Trees Minimizing Branching Costs
6: NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
7: From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
8: 3/2-Approximation for the Forest Augmentation Problem
9: Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
10: Cut-Preserving Vertex Sparsifiers for Planar and Quasi-bipartite Graphs
11: Improved Lower Bounds on the Expected Length of Longest Common Subsequences
12: Trace reconstruction from local statistical queries
13: Almost-linear Time Approximation Algorithm to Euclidean $k$-median and $k$-means
14: On the Houdr'e-Tetali conjecture about an isoperimetric constant of graphs
15: Learning-augmented Maximum Independent Set
16: Paralleling and Accelerating Arc Consistency Enforcement with Recurrent Tensor Computations
17: Speed-robust scheduling revisited
18: IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
19: Independent Set Reconfiguration Under Bounded-Hop Token
20: Text Indexing for Long Patterns using Locally Consistent Anchors
21: Faster Algorithms for Schatten-p Low Rank Approximation
22: Optimal Distance Labeling for Permutation Graphs
23: Optimal Padded Decomposition For Bounded Treewidth Graphs
24: A Unified Model of Congestion Games with Priorities: Two-Sided Markets with Ties, Finite and Non-Affine Delay Functions, and Pure Nash Equilibria
25: Engineering Fully Dynamic Exact $\Delta$-Orientation Algorithms
26: Exact Graph Matching in Correlated Gaussian-Attributed Erd\H{o}s-R'enyi Model
27: Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
28: R'enyi-infinity constrained sampling with $d^3$ membership queries
29: The Madness of Multiple Entries in March Madness
30: Optimal high-precision shadow estimation
31: Truthfulness of Calibration Measures
32: Hyper-Heuristics Can Profit From Global Variation Operators
33: Discrepancy Algorithms for the Binary Perceptron
34: Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs
35: Differential Privacy with Multiple Selections
36: Stochastic Online Metric Matching: Adversarial is no Harder than Stochastic
37: SquareSort: a cache-oblivious sorting algorithm
38: Thompson Sampling Itself is Differentially Private
39: Algorithms for Minimum Membership Dominating Set Problem
40: Interdiction of minimum spanning trees and other matroid bases