StringologyTimes

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

1: Shipper collaboration matching: fast enumeration of triangular transports with high cooperation effects
2: Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression
3: Matrix Perturbation: Davis-Kahan in the Infinity Norm
4: Mini-batch $k$-means terminates within $O(d/\epsilon)$ iterations
5: A greedy approach for increased vehicle utilization in ridesharing networks
6: $L$ is unequal $NL$ under the Strong Exponential Time Hypothesis
7: Algorithms for Construction, Classification and Enumeration of Closed Knight’s Paths
8: A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
9: Compressed Indexing for Consecutive Occurrences
10: Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
11: Fast Numerical Multivariate Multipoint Evaluation
12: Distribution Testing Under the Parity Trace
13: Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
14: A $d^{1/2+o(1)}$ Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids
15: Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
16: Minimum Cost Flow in the CONGEST Model
17: Algorithms for the Generalized Poset Sorting Problem
18: Dynamic treewidth
19: Mixing predictions for online metric algorithms
20: VC Set Systems in Minor-free (Di)Graphs and Applications
21: Connected and Autonomous Vehicle Scheduling Problems: Some Models and Algorithms
22: Chasing Positive Bodies
23: Strong spatial mixing for colorings on trees and its algorithmic applications
24: Online Time-Windows TSP with Predictions
25: Set Covering with Our Eyes Wide Shut
26: Determinantal Sieving
27: The Bit Complexity of Efficient Continuous Optimization
28: Sequential Linearithmic Time Optimal Unimodal Fitting When Minimizing Univariate Linear Losses
29: Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
30: Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models
31: Optimal Sketching Bounds for Sparse Linear Regression
32: The Laplacian Paradigm in Deterministic Congested Clique
33: On the Power of Threshold-Based Algorithms for Detecting Cycles in the CONGEST Model
34: Fast computation of approximate weak common intervals in multiple indeterminate strings
35: Spectral Toolkit of Algorithms for Graphs: Technical Report (1)
36: Improved Analysis of two Algorithms for Min-Weighted Sum Bin Packing
37: A Simple 1.5-Approximation Algorithm for a Wide Range of Max-SMTI Problems
38: Query lower bounds for log-concave sampling
39: Agnostic proper learning of monotone functions: beyond the black-box correction barrier
40: LSketch: A Label-Enabled Graph Stream Sketch Toward Time-Sensitive Queries
41: Parameterized Approximation Schemes for Clustering with General Norm Objectives
42: On the tractability of sampling from the Potts model at low temperatures via Swendsen–Wang dynamics
43: Krylov Methods are (nearly) Optimal for Low-Rank Approximation
44: Parameterized algorithms for Eccentricity Shortest Path Problem
45: Leveraging Reusability: Improved Competitive Ratio of Greedy for Reusable Resources
46: Convex Minimization with Integer Minima in $\widetilde O(n^4)$ Time
47: Temporalizing digraphs via linear-size balanced bi-trees