StringologyTimes

Data Structures and Algorithms: 2023/7/22-28

1: Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
2: Formal Concept Lattice Representations and Algorithms for Hypergraphs
3: Efficient Algorithms and Hardness Results for the Weighted $k$-Server Problem
4: Spectral Normalized-Cut Graph Partitioning with Fairness Constraints
5: Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
6: Agreement forests of caterpillar trees: complexity, kernelization and branching
7: Shorter and faster than Sort3AlphaDev
8: Treebar Maps: Schematic Representation of Networks at Scale
9: Fast Consistent Hashing in Constant Time
10: Tight Approximations for Graphical House Allocation
11: A faster and simpler algorithm for learning shallow networks
12: Correcting matrix products over the ring of integers
13: Knapsack: Connectedness, Path, and Shortest-Path
14: Optimality of Glauber dynamics for general-purpose Ising model sampling and free energy approximation
15: Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
16: Shortest two disjoint paths in conservative graphs
17: A 1.5-pproximation algorithms for activating 2 disjoint $st$-paths
18: Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials
19: A Statistical View of Column Subset Selection
20: Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling
21: On the Relationship Between Several Variants of the Linear Hashing Conjecture
22: Improved Digital Quantum Simulation by Non-Unitary Channels
23: Detection of Common Subtrees with Identical Label Distribution
24: Estimating Single-Node PageRank in $\tilde{O}\left(\min{d_t, \sqrt{m}}\right)$ Time
25: Online Maximum Independent Set of Hyperrectangles
26: Federated Heavy Hitter Recovery under Linear Sketching
27: Noisy k-means++ Revisited
28: A Compact DAG for Storing and Searching Maximal Common Subsequences
29: Fully Dynamic Consistent $k$-Center Clustering
30: Upward Planarity Testing of Biconnected Outerplanar DAGs Solves Partition
31: On the hardness of finding balanced independent sets in random bipartite graphs
32: On Minimizing Generalized Makespan on Unrelated Machines
33: Fast algorithms for k-submodular maximization subject to a matroid constraint
34: Hypergraph Isomorphism Computation
35: A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
36: A Sampling Lov'{a}sz Local Lemma for Large Domain Sizes
37: Evaluating Regular Path Queries on Compressed Adjacency Matrices
38: Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
39: 3-Coloring $C_4$ or $C_3$-free Diameter Two Graphs
40: Learning in Repeated Multi-Unit Pay-As-Bid Auctions
41: Dynamic algorithms for k-center on graphs