StringologyTimes

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

1: Computing Bend-Minimum Orthogonal Drawings of Plane Series-Parallel Graphs in Linear Time
2: A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
3: Polynomial formulations as a barrier for reduction-based hardness proofs
4: Efficient Algorithms for Planning with Participation Constraints
5: Hyperdimensional Hashing: A Robust and Efficient Dynamic Hash Table
6: A faster algorithm for Vertex Cover parameterized by solution size
7: Narrowing the LOCAL$\unicode{x2013}$CONGEST Gaps in Sparse Networks via Expander Decompositions
8: Deterministic 3-Server on a Circle and the Limitation of Canonical Potentials
9: Bankrupting DoS Attackers
10: Improved Utility Analysis of Private CountSketch
11: Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
12: Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails
13: New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
14: DPO: Dynamic-Programming Optimization on Hybrid Constraints
15: The Energy Complexity of Las Vegas Leader Election
16: Improved Online Contention Resolution for Matchings and Applications to the Gig Economy
17: Customizing ML Predictions for Online Algorithms
18: A Regression Approach to Learning-Augmented Online Algorithms
19: On data reduction for dynamic vector bin packing
20: Dynamic Resource Allocation: Algorithmic Design Principles and Spectrum of Achievable Performances
21: Reconfiguration of Digraph Homomorphisms
22: Frequency-Competitive Query Strategies to Maintain Low Congestion Potential Among Moving Entities
23: Deterministic Near-Optimal Distributed Listing of Cliques
24: Dynamic SAFFRON: Disease Control Over Time Via Group Testing
25: Primrose: Selecting Container Data Types by Their Properties
26: The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics
27: Estimation of Entropy in Constant Space with Improved Sample Complexity
28: DPER: Dynamic Programming for Exist-Random Stochastic SAT
29: Differentially Private Linear Sketches: Efficient Implementations and Applications
30: Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions
31: Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A(star) Search
32: Parameterized Complexity of Weighted Multicut in Trees
33: Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
34: Individual Fairness in Prophet Inequalities