StringologyTimes

Data Structures and Algorithms: 2022/9/22-28

1: Quasipolynomial-time algorithms for Gibbs point processes
2: Chaining, Group Leverage Score Overestimates, and Fast Spectral Hypergraph Sparsification
3: Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
4: A cubic algorithm for computing the Hermite normal form of a nonsingular integer matrix
5: Popular Edges with Critical Nodes
6: Efficiently Reconfiguring a Connected Swarm of Labeled Robots
7: Canadian Traveller Problem with Predictions
8: Uniform Reliability for Unbounded Homomorphism-Closed Graph Queries
9: Improved Approximation Algorithms by Generalizing the Primal-Dual Method Beyond Uncrossable Functions
10: From String Detection to Orthogonal Vector Problem
11: Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
12: Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
13: An Efficient Algorithm for Fair Multi-Agent Multi-Armed Bandit with Low Regret
14: The Online Knapsack Problem with Departures
15: Online Admission Control and Rebalancing in Payment Channel Networks
16: Non-monotonic Resource Utilization in the Bandits with Knapsacks Problem
17: Improving the Bounds of the Online Dynamic Power Management Problem
18: Twin-width V: linear minors, modular counting, and matrix multiplication
19: Compressing bipartite graphs with a dual reordering scheme
20: Optimal Efficiency-Envy Trade-Off via Optimal Transport
21: On the Cryptomorphism between Davis’ Subset Lattices, Atomic Lattices, and Closure Systems under T1 Separation Axiom
22: Augmentation based Approximation Algorithms for Flexible Network Design
23: Constant-delay enumeration for SLP-compressed documents
24: Random graph matching at Otter’s threshold via counting chandeliers
25: Package Delivery Using Drones with Restricted Movement Areas
26: Tree decompositions with bounded independence number: beyond independent sets
27: On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
28: Inferring Strings from Position Heaps in Linear Time
29: Obstructions to faster diameter computation: Asteroidal sets
30: On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization
31: On the Parameterized Intractability of Determinant Maximization
32: TGLib: An Open-Source Library for Temporal Graph Analysis
33: Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps
34: Approximate Description Length, Covering Numbers, and VC Dimension
35: How to Sample From The Limiting Distribution of a Continuous-Time Quantum Walk
36: Quantum-Inspired Perfect Matching under Vertex-Color Constraints
37: An $O(3.82^k)$ Time FPT Algorithm for Convex Flip Distance
38: Partial and Simultaneous Transitive Orientations via Modular Decomposition
39: A Quantum Optimization Algorithm for Single Machine Total Weighted Tardiness Minimization
40: Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers
41: From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds
42: Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity
43: Adaptive Out-Orientations with Applications
44: Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs
45: Time and Energy Efficient Contention Resolution in Asynchronous Shared Channels
46: Quantum Subroutine Composition