StringologyTimes

Data Structures and Algorithms: 2024/7/01-07

1: Balanced Learned Sort: a new learned model for fast and balanced item bucketing
2: Sampling from the Continuous Random Energy Model in Total Variation Distance
3: Efficient algorithms for computing bisimulations for nondeterministic fuzzy transition systems
4: Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turz'ik Bound
5: Validation and Implementation of ILBFS
6: Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact
7: Superconstant Inapproximability of Decision Tree Learning
8: Graph Spanners for Group Steiner Distances
9: Kick the cliques
10: From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
11: Spanner for the $0/1/\infty$ weighted region problem
12: Online Unbounded Knapsack
13: On polynomial kernelization for Stable Cutset
14: Minsum Problem for Discrete and Weighted Set Flow on Dynamic Path Network
15: Finer-Grained Hardness of Kernel Density Estimation
16: Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion
17: Linear Submodular Maximization with Bandit Feedback
18: Optimizing Information Access in Networks via Edge Augmentation
19: Matching (Multi)Cut: Algorithms, Complexity, and Enumeration
20: Finding Spanning Trees with Perfect Matchings
21: An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
22: Matroid Intersection under Minimum Rank Oracle
23: Nearly Linear Sparsification of $\ell_p$ Subspace Approximation
24: Greedy on Preorder is Linear for Preorder Initial Tree
25: Algorithmic Results for Weak Roman Domination Problem in Graphs
26: Quantum spectral method for gradient and Hessian estimation
27: Multiway Cuts with a Choice of Representatives
28: Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
29: Fair Repetitive Interval Scheduling
30: Improved Outerplanarity Bounds for Planar Graphs
31: A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
32: Reconfiguration of Independent Transversals
33: Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
34: Improved algorithms for learning quantum Hamiltonians, via flat polynomials
35: Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
36: The Degree of Fairness in Efficient House Allocation
37: Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
38: Near-optimal hierarchical matrix approximation from matrix-vector products
39: A Decomposition Theorem for Dynamic Flows
40: Agnostic Private Density Estimation via Stable List Decoding
41: Fair Submodular Cover
42: The Submodular Santa Claus Problem
43: Faster single-source shortest paths with negative real weights via proper hop distance
44: A linear-time algorithm for $(1+\epsilon)\Delta$-edge-coloring
45: Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning
46: Universal Perfect Samplers for Incremental Streams
47: Counting Permutation Patterns with Multidimensional Trees
48: Congestion-Approximators from the Bottom Up
49: FPTAS for Holant Problems with Log-Concave Signatures
50: Fr'echet Distance in Subquadratic Time
51: Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses
52: Competitive Analysis of Online Path Selection: Impacts of Path Length, Topology, and System-Level Costs
53: Online Matching: A Brief Survey