StringologyTimes

Data Structures and Algorithms: 2019/5/15-21

1: Online Computation with Untrusted Advice
2: List-Decodable Linear Regression
3: Restricted Max-Min Allocation: Approximation and Integrality Gap
4: Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering
5: Two-sided profile-based optimality in the stable marriage problem
6: Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs
7: Time-Energy Tradeoffs for Evacuation by Two Robots in the Wireless Model
8: Scalable Graph Embeddings via Sparse Transpose Proximities
9: Speeding up the Karatsuba algorithm
10: Separating Structure from Noise in Large Graphs Using the Regularity Lemma
11: Stay or Switch: Competitive Online Algorithms for Energy Plan Selection in Energy Markets with Retail Choice
12: Parallel decompression of gzip-compressed files and random access to DNA sequences
13: Randomization of Approximate Bilinear Computation for Matrix Multiplication
14: Shortest Path Algorithms between Theory and Practice
15: Lasserre Integrality Gaps for Graph Spanners and Related Problems
16: Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
17: Massively Parallel Computation via Remote Memory Access
18: Covering Metric Spaces by Few Trees
19: The NP-hard problem of computing the maximal sample variance over interval data is solvable in almost linear time with high probability
20: Robust Online Algorithms for Dynamic Problems
21: Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
22: Prefix Block-Interchanges on Binary and Ternary Strings
23: Inference under Information Constraints II: Communication Constraints and Shared Randomness
24: Locally Differentially Private Frequency Estimation with Consistency
25: Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation
26: Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
27: Silent MST approximation for tiny memory
28: Approximation results for makespan minimization with budgeted uncertainty
29: Shortest-Path-Preserving Rounding
30: Fast Computing the Algebraic Degree of Boolean Functions
31: An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint