StringologyTimes

Data Structures and Algorithms: 2022/4/01-07

1: Fair Short Paths in Vertex-Colored Graphs
2: Prefix Filter: Practically and Theoretically Better Than Bloom
3: Instability of backoff protocols with arbitrary arrival rates
4: Balanced Clique Computation in Signed Networks: Concepts and Algorithms
5: Double-Hashing Algorithm for Frequency Estimation in Data Streams
6: Twin-width VIII: delineation and win-wins
7: Improved Approximation Algorithm for Graph Burning on Trees
8: Various proofs of the Fundamental Theorem of Markov Chains
9: An Optimal Algorithm for Certifying Monotone Functions
10: Logistics in the Sky: A Two-phase Optimization Approach for the Drone Package Pickup and Delivery System
11: Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
12: Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
13: Optimal Workplace Occupancy Strategies during the COVID-19 Pandemic
14: Sampling Lov'asz Local Lemma For General Constraint Satisfaction Solutions In Near-Linear Time
15: Using random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials
16: The Fast Johnson-Lindenstrauss Transform is Even Faster
17: Multitasking Scheduling with Shared Processing
18: Almost-Linear Planted Cliques Elude the Metropolis Process
19: Algorithms for the ferromagnetic Potts model on expanders
20: Online matching games in bipartite expanders and applications
21: Randomized matrix-free quadrature for spectrum and spectral sum approximation
22: Streaming Algorithms for Multitasking Scheduling with Shared Processing
23: Streaming Approximation Scheme for Minimizing Total Completion Time on Parallel Machines Subject to Varying Processing Capacity
24: Streaming Facility Location in High Dimension via Geometric Hashing
25: Simulated Annealing is a Polynomial-Time Approximation Scheme for the Minimum Spanning Tree Problem
26: Computing in Anonymous Dynamic Networks Is Linear
27: All-Pairs Shortest Path Distances with Differential Privacy: Improved Algorithms for Bounded and Unbounded Weights
28: Maintaining Expander Decompositions via Sparse Cuts
29: Nearly Tight Spectral Sparsification of Directed Hypergraphs by a Simple Iterative Sampling Algorithm
30: Quantum Approximate Counting for Markov Chains and Application to Collision Counting
31: Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
32: A Generic Closed-form Optimal Step-size for ADMM
33: Scheduling Coflows for Minimizing the Total Weighted Completion Time in Identical Parallel Networks
34: Disentangling the Computational Complexity of Network Untangling
35: Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings
36: Approximation Algorithms and Hardness for $n$-Pairs Shortest Paths and All-Nodes Shortest Cycles
37: Faster Pattern Matching under Edit Distance
38: Speeding Up Sparsification using Inner Product Search Data Structures
39: Lower Bounds for Restricted Schemes in the Two-Adaptive Bitprobe Model
40: Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case