StringologyTimes

Data Structures and Algorithms: 2023/12/01-07

1: Structural results for the Tree Builder Random Walk
2: First-Order Model Checking on Monadically Stable Graph Classes
3: A Threshold Greedy Algorithm for Noisy Submodular Maximization
4: Online Graph Coloring with Predictions
5: Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
6: Disjoint Dominating and 2-Dominating Sets in Graphs: Hardness and Approximation results
7: Suffixient Sets
8: A Tight Lower Bound for 3-Coloring Grids in the Online-LOCAL Model
9: Moderate Dimension Reduction for $k$-Center Clustering
10: Finding and counting small tournaments in large tournaments
11: Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regression
12: Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable
13: Faster Sublinear-Time Edit Distance
14: Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
15: The Intractability of the Picker Routing Problem
16: Isomorphism for Tournaments of Small Twin Width
17: Inapproximability of Maximum Diameter Clustering for Few Clusters
18: Hot PATE: Private Aggregation of Distributions for Diverse Task
19: Connected Components in Linear Work and Near-Optimal Time
20: Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
21: Embedding Probability Distributions into Low Dimensional $\ell_1$: Tree Ising Models via Truncated Metrics
22: On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental
23: Simple and fast Algorithm for Finding Roots of Error-Locator Polynomials: Modulus Search
24: Edge coloring of products of signed graphs
25: Improved Algorithms for Minimum-Membership Geometric Set Cover
26: A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
27: Streaming Algorithms for the $k$-Submodular Cover Problem
28: Testing Connectedness of Images
29: A Tight Threshold Bound for Search Trees with 2-way Comparisons
30: Computing the Volume of a Restricted Independent Set Polytope Deterministically
31: PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search
32: The sample complexity of multi-distribution learning
33: Approximating the Graph Edit Distance with Compact Neighborhood Representations
34: Distances and shortest paths on graphs of bounded highway dimension: simple, fast, dynamic