StringologyTimes

Data Structures and Algorithms: 2024/3/08-14

1: Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
2: Optimizing Inventory Placement for a Downstream Online Matching Problem
3: Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation
4: On $[1,2]$-Domination in Interval and Circle Graphs
5: A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
6: SQ Lower Bounds for Non-Gaussian Component Analysis with Weaker Assumptions
7: Improved Lower Bound for Differentially Private Facility Location
8: A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets
9: NP-Completeness for the Space-Optimality of Double-Array Tries
10: A basic lower bound for property testing
11: Data-Dependent LSH for the Earth Mover’s Distance
12: Single Family Algebra Operation on BDDs and ZDDs Leads To Exponential Blow-Up
13: Efficient Algorithms for Personalized PageRank Computation: A Survey
14: Dynamic Convex Hulls for Simple Paths
15: Scalable $k$-clique Densest Subgraph Search
16: Approximate Bipartite $b$-Matching using Multiplicative Auction
17: Hamiltonicity, Path Cover, and Independence Number: An FPT Perspective
18: Revisiting Path Contraction and Cycle Contraction
19: Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
20: Accelerating Sparse Tensor Decomposition Using Adaptive Linearized Representation
21: Fun Maximizing Search, (Non) Instance Optimality, and Video Games for Parrots
22: An Algorithm for Correct Computation of Reeb Spaces for PL Bivariate Fields
23: Arborescences and Shortest Path Trees when Colors Matter
24: Balanced Substructures in Bicolored Graphs
25: Optimal Bounds for Distinct Quartics
26: Approximating Maximum Edge 2-Coloring by Normalizing Graphs
27: Noisy Computing of the Threshold Function
28: The Primal Pathwidth SETH
29: Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
30: Learning-Augmented Algorithms with Explicit Predictors
31: Shining Light on Periodic Dominating Sets in Bounded-Treewidth Graphs
32: Controlling Delegations in Liquid Democracy
33: Maximum Defective Clique Computation: Improved Time Complexities and Practical Performance
34: Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing
35: Simplified Tight Bounds for Monotone Minimal Perfect Hashing
36: Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
37: Highway Preferential Attachment Models for Geographic Routing
38: The Runtime of Random Local Search on the Generalized Needle Problem
39: A bargain for mergesorts (functional pearl) – How to prove your mergesort correct and stable, almost for free
40: Height-bounded Lempel-Ziv encodings
41: Worst-Case to Expander-Case Reductions: Derandomized and Generalized
42: Improved Randomized Approximation of Hard Universality and Emptiness Problems
43: Efficiently Computing Similarities to Private Datasets
44: Two-sided Assortment Optimization: Adaptivity Gaps and Approximation Algorithms
45: Approximating Small Sparse Cuts
46: Efficient size-prescribed $k$-core search
47: A Short Review on Novel Approaches for Maximum Clique Problem: from Classical algorithms to Graph Neural Networks and Quantum algorithms