StringologyTimes

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

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