StringologyTimes

Data Structures and Algorithms: 2021/1/15-21

1: No-go Theorem for Acceleration in the Hyperbolic Plane
2: Minimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instances
3: Group Testing with a Graph Infection Spread Model
4: An Improved Approximation Algorithm for the Minimum $k$-Edge Connected Multi-Subgraph Problem
5: New Approximation Algorithms for Forest Closeness Centrality – for Individual Vertices and Vertex Groups
6: Solving one variable word equations in the free group in cubic time
7: The Complexity of Bicriteria Tree-Depth
8: Data stream fusion for accurate quantile tracking and analysis
9: An FPT algorithm for Matching Cut and d-cut
10: Time-Efficient and High-Quality Graph Partitioning for Graph Dynamic Scaling
11: Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
12: PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts
13: Revisiting the Auction Algorithm for Weighted Bipartite Perfect Matchings
14: Maximizing approximately k-submodular functions
15: Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
16: Dynamic Longest Increasing Subsequence and the Erd"{o}s-Szekeres Partitioning Problem
17: Locality-Sensitive Orderings and Applications to Reliable Spanners
18: Subspace exploration: Bounds on Projected Frequency Estimation
19: Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
20: Local Complexity of Polygons
21: Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs
22: Anticoncentration versus the number of subset sums
23: Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
24: Colouring Graphs of Bounded Diameter in the Absence of Small Cycles
25: Star Discrepancy Subset Selection: Problem Formulation and Efficient Approaches for Low Dimensions
26: Inference under Information Constraints III: Local Privacy Constraints
27: Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
28: A Fast Optimal Double Row Legalization Algorithm
29: Improved Algorithms for the General Exact Satisfiability Problem