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: Accurate Analysis of Sparse Random Projections
30: Fair Repetitive Interval Scheduling
31: Improved Outerplanarity Bounds for Planar Graphs
32: A $\frac{4}{3}$-Approximation for the Maximum Leaf Spanning Arborescence Problem in DAGs
33: Reconfiguration of Independent Transversals
34: Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
35: Improved algorithms for learning quantum Hamiltonians, via flat polynomials
36: Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
37: The Degree of Fairness in Efficient House Allocation
38: Rapid Mixing via Coupling Independence for Spin Systems with Unbounded Degree
39: Near-optimal hierarchical matrix approximation from matrix-vector products
40: A Decomposition Theorem for Dynamic Flows
41: Agnostic Private Density Estimation for GMMs via List Global Stability
42: Fair Submodular Cover
43: The Submodular Santa Claus Problem
44: Faster single-source shortest paths with negative real weights via proper hop distance
45: A linear-time algorithm for $(1+\epsilon)\Delta$-edge-coloring
46: Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning
47: Universal Perfect Samplers for Incremental Streams
48: Counting Permutation Patterns with Multidimensional Trees
49: Congestion-Approximators from the Bottom Up
50: FPTAS for Holant Problems with Log-Concave Signatures
51: Fr'echet Distance in Subquadratic Time
52: Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses
53: Competitive Analysis of Online Path Selection: Impacts of Path Length, Topology, and System-Level Costs
54: Online Matching: A Brief Survey