StringologyTimes

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

1: Replicable Learning of Large-Margin Halfspaces
2: Diversity-Aware $k$-Maximum Inner Product Search Revisited
3: A Uniformly Random Solution to Algorithmic Redistricting
4: Practical algorithms for Hierarchical overlap graphs
5: Robust recovery for stochastic block models, simplified and generalized
6: A $(5/3+{\epsilon})$-Approximation for Tricolored Non-crossing Euclidean TSP
7: On Distributed Computation of the Minimum Triangle Edge Transversal
8: Chasing Convex Functions with Long-term Constraints
9: Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
10: Masked Matrix Multiplication for Emergent Sparsity
11: Random-Order Online Independent Set of Intervals and Hyperrectangles
12: Sample-Efficient Linear Regression with Self-Selection Bias
13: Locality Bounds for Sampling Hamming Slices
14: Parameterized Complexity of Finding Dissimilar Shortest Paths
15: An Improved Pseudopolynomial Time Algorithm for Subset Sum
16: Approximate Circular Pattern Matching under Edit Distance
17: Time Efficient Implementation for Online $k$-server Problem on Trees
18: Hitting Meets Packing: How Hard Can it Be?
19: Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
20: Tight Inapproximability of Target Set Reconfiguration
21: The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
22: The Cost of Parallelizing Boosting
23: Algorithmically Fair Maximization of Multiple Submodular Objective Functions
24: Platforms for Efficient and Incentive-Aware Collaboration
25: Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
26: Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
27: Graph Partitioning With Limited Moves
28: On the Complexity of Community-aware Network Sparsification
29: Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
30: Tree decompositions meet induced matchings: beyond Max Weight Independent Set
31: An $O(n \log n)$-Time Approximation Scheme for Geometric Many-to-Many Matching
32: List Coloring of some Cayley graphs using Kernel perfections
33: Online Drone Scheduling for Last-mile Delivery
34: Honeybee: Byzantine Tolerant Decentralized Peer Sampling with Verifiable Random Walks
35: Enhanced Graph Pattern Matching
36: Problems on Group-labeled Matroid Bases
37: Algorithms for Halfplane Coverage and Related Problems
38: A Provably Accurate Randomized Sampling Algorithm for Logistic Regression
39: An optimal tradeoff between entanglement and copy complexity for state tomography
40: Parameterized and approximation algorithms for coverings points with segments in the plane
41: A fast implementation of the good-suffix array for the Boyer-Moore string matching algorithm
42: The Bottom-Left Algorithm for the Strip Packing Problem
43: The Complexity of Diameter on H-free graphs
44: The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
45: inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition
46: Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability
47: Energy-Efficient Scheduling with Predictions
48: Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms
49: Scalable and Interpretable Identification of Minimal Undesignable RNA Structure Motifs with Rotational Invariance
50: On the probability of a Pareto record
51: Sharpened localization of the trailing point of the Pareto record frontier
52: Enclosing Points with Geometric Objects
53: Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
54: Shortest cover after edit
55: PureLottery: Fair and Bias-Resistant Leader Election with a Novel Single-Elimination Tournament Algorithm
56: FlipHash: A Constant-Time Consistent Range-Hashing Algorithm
57: Deterministic Cache-Oblivious Funnelselect
58: The SMART approach to instance-optimal online learning
59: Learning-Based Algorithms for Graph Searching Problems
60: Robustly Learning Single-Index Models via Alignment Sharpness
61: Decremental $(1+\epsilon)$-Approximate Maximum Eigenvector: Dynamic Power Method
62: Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
63: Computing Minimal Absent Words and Extended Bispecial Factors with CDAWG Space
64: Lower Bounds for Leaf Rank of Leaf Powers
65: Max-Cut with $\epsilon$-Accurate Predictions
66: Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
67: Fractional Linear Matroid Matching is in quasi-NC
68: Online Edge Coloring is (Nearly) as Easy as Offline
69: Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
70: COPR – Efficient, large-scale log storage and retrieval