StringologyTimes

Data Structures and Algorithms: 2025/11/01-07

1: Learned Static Function Data Structures
2: Rateless Bloom Filters: Set Reconciliation for Divergent Replicas with Variable-Sized Elements
3: Scheduling Problems with Constrained Rejections
4: Uncrossed Multiflows and Applications to Disjoint Paths
5: An Approximation Algorithm for Monotone Submodular Cost Allocation
6: Fast Stochastic Greedy Algorithm for $k$-Submodular Cover Problem
7: SpEx: A Spectral Approach to Explainable Clustering
8: Fast Answering Pattern-Constrained Reachability Queries with Two-Dimensional Reachability Index
9: Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
10: Fault-Tolerant Approximate Distance Oracles with a Source Set
11: Subtree Mode and Applications
12: NP-membership for the boundary-boundary art-gallery problem
13: Robust Streaming Against Low-Memory Adversaries
14: Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
15: Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint
16: Probabilistic Graph Cuts
17: Learning CNF formulas from uniform random solutions in the local lemma regime
18: Accelerating Graph Similarity Search through Integer Linear Programming
19: A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
20: Mixing of general biased adjacent transposition chains
21: Faster Weak Expander Decompositions and Approximate Max Flow
22: Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
23: The Contiguous Art Gallery Problem is in {\Theta}(n log n)
24: Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
25: Min-Max Optimization Is Strictly Easier Than Variational Inequalities
26: A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
27: Optimal Stopping with a Predicted Prior
28: Improved Online Load Balancing in the Two-Norm
29: Hesse’s Redemption: Efficient Convex Polynomial Programming
30: Dynamic Meta-Kernelization
31: Online Flow Time Minimization: Tight Bounds for Non-Preemptive Algorithms
32: Randomized Rounding over Dynamic Programs
33: Engineering Algorithms for $\ell$-Isolated Maximal Clique Enumeration
34: Attractors Is All You Need: Parity Games In Polynomial Time
35: Non-Monotonicity in Fair Division of Graphs
36: Improved Bounds with a Simple Algorithm for Edge Estimation for Graphs of Unknown Size
37: Efficient Testing Implies Structured Symmetry
38: An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
39: Multi-Pass Streaming Lower Bounds for Uniformity Testing
40: HART: A Hybrid Addressing Scheme for Self-Balancing Binary Search Trees in Phase Change Memory (PCM)
41: A Characterization of List Language Identification in the Limit
42: Depth-13 Sorting Networks for 28 Channels
43: A High-Throughput GPU Framework for Adaptive Lossless Compression of Floating-Point Data
44: Counting Patterns in Degenerate Graphs in Constant Space
45: Estimating Hitting Times Locally At Scale
46: A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
47: Free-order secretary for two-sided independence systems
48: Online Algorithms for Repeated Optimal Stopping: Achieving Both Competitive Ratio and Regret Bounds
49: Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
50: Improved Additive Approximation Algorithms for APSP
51: Optimal Parallel Basis Finding in Graphic and Related Matroids
52: Tight Bounds for Sampling q-Colorings via Coupling from the Past
53: Awesome graph parameters
54: Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations