StringologyTimes

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

1: BEER: Fast $O(1/T)$ Rate for Decentralized Nonconvex Optimization with Communication Compression
2: Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings
3: An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
4: Quantum machine learning with subspace states
5: DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample Complexity
6: Recursive Multi-Section on the Fly: Shared-Memory Streaming Algorithms for Hierarchical Graph Partitioning and Process Mapping
7: Exact Matrix Factorization Updates for Nonlinear Programming
8: Testability and local certification of monotone properties in minor-closed classes
9: New Characterizations of Core Imputations of Matching and $b$-Matching Games
10: Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
11: Nonlinear Initialization Methods for Low-Rank Neural Networks
12: Modification Problems toward Proper (Helly) Circular-arc Graphs
13: Matching Orderable and Separable Hypergraphs
14: 3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation
15: Improved quantum algorithms for linear and nonlinear differential equations
16: A New Temporal Interpretation of Cluster Editing
17: Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
18: Passing the Limits of Pure Local Search for Weighted $k$-Set Packing
19: Principled Graph Management
20: Fair Representation Clustering with Several Protected Classes
21: Fast and explainable clustering based on sorting
22: Perpetual maintenance of machines with different urgency requirements
23: Even Simpler Deterministic Matrix Sketching
24: On constant-time quantum annealing and guaranteed approximations for graph optimization problems
25: Multivariate Algorithmics for Eliminating Envy by Donating Goods
26: Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan
27: Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space
28: Globally Minimal Defensive Alliances: A Parameterized Perspective
29: Lossy Planarization: A Constant-Factor Approximate Kernelization for Planar Vertex Deletion
30: Challenges for quantum computation of nonlinear dynamical systems using linear representations
31: Flow Time Scheduling and Prefix Beck-Fiala
32: Log-Sobolev inequality for near critical Ising models
33: Faster exact solution of sparse MaxCut and QUBO problems
34: Logarithmic equal-letter runs for BWT of purely morphic words
35: Leveraging the Power of Graph Algorithms: Efficient Algorithms for Computer-Aided Verification
36: Improved Bounds for Fractional Online Matching Problems
37: Using Partial Monotonicity in Submodular Maximization
38: Longest Cycle above Erd\H{o}s-Gallai Bound
39: Effective Variable Depth Local Search for the Budgeted Maximum Coverage Problem
40: Almost Optimal Proper Learning and Testing Polynomials
41: Memory-Efficient Sequential Pattern Mining with Hybrid Tries