StringologyTimes

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

1: Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
2: Finding the root in random nearest neighbor trees
3: Overcomplete Tensor Decomposition via Koszul-Young Flattenings
4: Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals
5: Hardness Amplification for Dynamic Binary Search Trees
6: On Optimal Testing of Linearity
7: Construction and Preliminary Validation of a Dynamic Programming Concept Inventory
8: Sparsifying Suprema of Gaussian Processes
9: Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
10: Distributed Model Checking in Graphs Classes of Bounded Expansion
11: Quantum Algorithm for the Multiple String Matching Problem
12: Approximating Prize-Collecting Variants of TSP
13: Totally $\Delta$-modular IPs with two non-zeros in most rows
14: Tag arrays
15: Heavy-tailed Contamination is Easier than Adversarial Contamination
16: The Polymatroid Representation of a Greedoid, and Associated Galois Connections
17: Exploring Facets of Language Generation in the Limit
18: Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
19: Revenue Maximization in Choice-Based Matching Markets
20: Binary Search with Distributional Predictions
21: Directed Token Sliding
22: On the Robustness of the Successive Projection Algorithm
23: Scalable Fault-Tolerant MapReduce
24: Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
25: Bow Metrics and Hyperbolicity
26: Forest Covers and Bounded Forest Covers
27: Approximation Algorithms for Combinatorial Optimization with Predictions
28: Leakage-Robust Bayesian Persuasion
29: OPMOS: Ordered Parallel Algorithm for Multi-Objective Shortest-Paths
30: Optimized 2-Approximation of Treewidth
31: Online $b$-Matching with Stochastic Rewards
32: Enabling Skip Graphs to Process K-Dimensional Range Queries in a Mobile Sensor Network
33: Smoothed Analysis of the k-Swap Neighborhood for Makespan Scheduling
34: Weakly acyclic diagrams: A data structure for infinite-state symbolic verification
35: Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty
36: Dynamic data summarization for hierarchical spatial clustering
37: Arcee: An OCM-Solver
38: A Parallel Scan Algorithm in the Tensor Core Unit Model
39: Structural Parameterization of Locating-Dominating Set and Test Cover
40: Improved Parallel Derandomization via Finite Automata with Applications
41: A Faster Deterministic Algorithm for Mader’s $\mathcal{S}$-Path Packing
42: Undirected 3-Fault Replacement Path in Nearly Cubic Time
43: Extraction Theorems With Small Extraction Numbers
44: Parallel Token Swapping for Qubit Routing
45: Optimal root recovery for uniform attachment trees and $d$-regular growing trees
46: Online versus Offline Adversaries in Property Testing
47: Near-Optimal Trace Reconstruction for Mildly Separated Strings
48: Fast Schulze Voting Using Quickselect
49: Improved Approximation Algorithms for Flexible Graph Connectivity and Capacitated Network Design
50: Streaming Algorithms via Local Algorithms for Maximum Directed Cut
51: A Simple and Fast Algorithm for Fair Cuts