StringologyTimes

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

1: A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
2: Best $L_p$ Isotonic Regressions, $p \in {0, 1, \infty}$
3: Last Switch Dependent Bandits with Monotone Payoff Functions
4: Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem
5: Scaling Expected Force: Efficient Identification of Key Nodes in Network-based Epidemic Models
6: Algorithms Transcending the SAT-Symmetry Interface
7: Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance
8: Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise
9: Green Traffic Engineering by Line Card Minimization
10: Sharper Bounds for $\ell_p$ Sensitivity Sampling
11: Efficient Temporal Butterfly Counting and Enumeration on Temporal Bipartite Graphs
12: Dynamic Algorithms for Matroid Submodular Maximization
13: Improved Algorithms for Distance Selection and Related Problems
14: Fast Matrix Multiplication Without Tears: A Constraint Programming Approach
15: Labeled Interleaving Distance for Reeb Graphs
16: The Maximum Matrix Contraction Problem
17: Parameterized Complexity of Broadcasting in Graphs
18: Approximation schemes for capacity vehicle routing problems: A survey
19: Revisiting Garg’s 2-Approximation Algorithm for the k-MST Problem in Graphs
20: Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization
21: Auditable data structures: theory and applications
22: Provable benefits of score matching
23: Accelerating Personalized PageRank Vector Computation
24: On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms
25: On Approximability of Steiner Tree in $\ell_p$-metrics
26: Tight Regret Bounds for Single-pass Streaming Multi-armed Bandits
27: Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
28: Efficient Approximation Algorithms for Scheduling Coflows with Total Weighted Completion Time in Identical Parallel Networks
29: A Fast Algorithm for Computing Prefix Probabilities
30: Sparse Convolution for Approximate Sparse Instance
31: Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
32: Hyper-distance Oracles in Hypergraphs
33: Near-Optimal Quantum Coreset Construction Algorithms for Clustering
34: Fast Partitioned Learned Bloom Filter
35: Reducing Exposure to Harmful Content via Graph Rewiring
36: On the Parameterized Complexity of Computing $st$-Orientations with Few Transitive Edges
37: Accelerating Range Minimum Queries with Ray Tracing Cores
38: Tracking Evolving labels using Cone based Oracles
39: A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems
40: Rigorous Runtime Analysis of MOEA/D for Solving Multi-Objective Minimum Weight Base Problems
41: Minimizing Hitting Time between Disparate Groups with Shortcut Edges
42: Representative set statements for delta-matroids and the Mader delta-matroid
43: Buying Information for Stochastic Optimization
44: Constant Sequence Extension for Fast Search Using Weighted Hamming Distance
45: Efficient Centrality Maximization with Rademacher Averages
46: One-sided Matrix Completion from Two Observations Per Row
47: Quantum Distance Calculation for $\epsilon$-Graph Construction
48: Matroid-Constrained Vertex Cover
49: Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
50: On Computing Optimal Tree Ensembles
51: Maintaining the cycle structure of dynamic permutations