StringologyTimes

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

1: The Sharp Power Law of Local Search on Expanders
2: Fusion Blossom: Fast MWPM Decoders for QEC
3: Fast and Efficient Matching Algorithm with Deadline Instances
4: New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
5: Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
6: Selective Population Protocols
7: A Sweep-plane Algorithm for Calculating the Isolation of Mountains
8: Privacy Auditing with One (1) Training Run
9: Geometric Hitting Set for Line-Constrained Disks and Related Problems
10: Sparsifying sums of norms
11: Interplay between Topology and Edge Weights in Real-World Graphs: Concepts, Patterns, and an Algorithm
12: Static Pricing Guarantees for Queueing Systems
13: Lower Bounds for Non-Adaptive Shortest Path Relaxation
14: Sorting and Hypergraph Orientation under Uncertainty with Predictions
15: Private Everlasting Prediction
16: Finding Maximal Exact Matches in Graphs
17: List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite Graphs
18: Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise
19: Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint
20: Cache-Oblivious Parallel Convex Hull in the Binary Forking Model
21: Online List Labeling with Predictions
22: The Complexity of Diagonalization
23: Fault-Tolerant Consensus in Quantum Networks
24: Online Resource Allocation in Episodic Markov Decision Processes
25: Submodularity Gaps for Selected Network Design and Matching Problems
26: Difference of Submodular Minimization via DC Programming
27: (Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
28: Parameterized Complexity of Equality MinCSP
29: Improved and Partially-Tight Lower Bounds for Message-Passing Implementations of Multiplicity Queues
30: Efficient quantum linear solver algorithm with detailed running costs
31: Approximate Distance Sensitivity Oracles in Subquadratic Space
32: Distributed MIS with Low Energy and Time Complexities
33: Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication
34: Tester-Learners for Halfspaces: Universal Algorithms
35: OPTWIN: Drift identification with optimal sub-windows
36: Stretch-width
37: Distortion in metric matching with ordinal preferences