StringologyTimes

Data Structures and Algorithms: 2020/2/08-14

1: List Decodable Subspace Recovery
2: The Bloom Tree
3: A General Coreset-Based Approach to Diversity Maximization under Matroid Constraints
4: Curvature of Feasible Sets in Offline and Online Optimization
5: On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm
6: Streaming Submodular Maximization under a $k$-Set System Constraint
7: Monotone probability distributions over the Boolean cube can be learned with sublinear samples
8: Optimal polynomial-time compression for Boolean Max CSP
9: Approximating Text-to-Pattern Distance via Dimensionality Reduction
10: Fair Correlation Clustering
11: Combinatorial Semi-Bandit in the Non-Stationary Environment
12: Approximation Algorithms for Steiner Tree Based on Star Contractions: A Unified View
13: Edge colouring Game on Trees with maximum degree $\Delta=4$
14: Palindromic k-Factorization in Pure Linear Time
15: Efficient Matrix Multiplication: The Sparse Power-of-2 Factorization
16: $2$-node-connectivity network design
17: On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness
18: Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
19: Maximizing Products of Linear Forms, and The Permanent of Positive Semidefinite Matrices
20: Learning and Sampling of Atomic Interventions from Observations
21: Optimizing Item and Subgroup Configurations for Social-Aware VR Shopping
22: Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
23: An Optimal Algorithm for Online Multiple Knapsack
24: A polynomial time parallel algorithm for graph isomorphism using a quasipolynomial number of processors
25: A simple certifying algorithm for 3-edge-connectivity
26: Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms
27: Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm
28: Positive Semidefinite Programming: Mixed, Parallel, and Width-Independent
29: Optimal Label Splitting for Embedding an LTS into an arbitrary Petri Net Reachability Graph is NP-complete
30: The {0,1}-knapsack problem with qualitative levels
31: On the I/O complexity of the k-nearest neighbor problem
32: Distributed and Adaptive Fast Multipole Method In Three Dimensions
33: Rubik Tables and Object Rearrangement
34: Eigenvector Component Calculation Speedup over NumPy for High-Performance Computing
35: Uniform Linked Lists Contraction
36: Optimal Multiple Stopping Rule for Warm-Starting Sequential Selection
37: The Complexity of Binary Matrix Completion Under Diameter Constraints
38: HushRelay: A Privacy-Preserving, Efficient, and Scalable Routing Algorithm for Off-Chain Payments
39: An Optimal Decentralized $(\Delta + 1)$-Coloring Algorithm
40: Parallel Batch-dynamic Trees via Change Propagation
41: List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time
42: Improved Classical and Quantum Algorithms for Subset-Sum
43: Assortment Optimization with Repeated Exposures and Product-dependent Patience Cost
44: Distributed Graph Realizations
45: Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning
46: A quasi-polynomial algorithm for well-spaced hyperbolic TSP
47: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
48: Fast Convergence for Langevin Diffusion with Manifold Structure
49: Drawing Graphs as Spanners
50: Engineering Faster Sorters for Small Sets of Items
51: On Two Measures of Distance between Fully-Labelled Trees
52: Learning Halfspaces with Massart Noise Under Structured Distributions
53: Work-efficient Batch-incremental Minimum Spanning Trees with Applications to the Sliding Window Model
54: Online Algorithms for Multi-shop Ski Rental with Machine Learned Advice
55: A Breezing Proof of the KMW Bound
56: A Simple 1-1/e Approximation for Oblivious Bipartite Matching