StringologyTimes

Data Structures and Algorithms: 2021/2/22-28

1: Mining EL Bases with Adaptable Role Depth
2: Temporal Reachability Minimization: Delaying vs. Deleting
3: Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time
4: A High-dimensional Sparse Fourier Transform in the Continuous Setting
5: The Randomized Competitive Ratio of Weighted $k$-server is at least Exponential
6: Recent Advances in Fully Dynamic Graph Algorithms
7: Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs
8: Quantum query complexity with matrix-vector products
9: Partially Optimal Edge Fault-Tolerant Spanners
10: Robust $k$-Center with Two Types of Radii
11: Optimal Sorting Circuits for Short Keys
12: Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT
13: Massively Parallel Correlation Clustering in Bounded Arboricity Graphs
14: Testing Hamiltonicity (and other problems) in Minor-Free Graphs
15: The Power of $D$-hops in Matching Power-Law Graphs
16: Conditional Lower Bounds for Variants of Dynamic LIS
17: Instance Specific Approximations for Submodular Maximization
18: Kronecker Products, Low-Depth Circuits, and Matrix Rigidity
19: SoK: A Taxonomy for Critical Analysis of Consensus Mechanisms in Consortium Blockchain
20: Lossless Compression of Efficient Private Local Randomizers
21: Density Sketches for Sampling and Estimation
22: Learning-Augmented Sketches for Hessians
23: Approximability of all Boolean CSPs with linear sketches
24: SALSA: Self-Adjusting Lean Streaming Analytics
25: A New Algorithm for Euclidean Shortest Paths in the Plane
26: Random Graphs with Prescribed $K$-Core Sequences: A New Null Model for Network Analysis
27: Approximate Privacy-Preserving Neighbourhood Estimations
28: Spanning Tree Constrained Determinantal Point Processes are Hard to (Approximately) Evaluate
29: Algorithms and Complexity on Indexing Founder Graphs
30: A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
31: Coalgebra Encoding for Efficient Minimization
32: A Refined Analysis of Submodular Greedy
33: Generalized Parametric Path Problems
34: Toward Instance-Optimal State Certification With Incoherent Measurements
35: Semidefinite Relaxations of Products of Nonnegative Forms on the Sphere
36: On Register Linearizability and Termination
37: Can Romeo and Juliet Meet? Or Rendezvous Games with Adversaries on Graphs
38: Optimal Online Peak Minimization Using Energy Storage
39: An Optimal Deterministic Algorithm for Geodesic Farthest-Point Voronoi Diagrams in Simple Polygons
40: Periodic trajectories in P-time event graphs and the non-positive circuit weight problem
41: Discovering Dense Correlated Subgraphs in Dynamic Networks
42: Weighted Ancestors in Suffix Trees Revisited
43: On the Approximation Ratio of the 3-Opt Algorithm for the (1,2)-TSP