StringologyTimes

Data Structures and Algorithms: 2019/2/22-28

1: The Arboricity Captures the Complexity of Sampling Edges
2: On the qubit routing problem
3: Online Sampling from Log-Concave Distributions
4: Covering a tree with rooted subtrees
5: Local Computation Algorithms for Spanners
6: A time-distance trade-off for GDD with preprocessing—Instantiating the DLW heuristic
7: A simple upper bound for trace function of a hypergraph with applications
8: Preconditioning for the Geometric Transportation Problem
9: Nonconvex sampling with the Metropolis-adjusted Langevin algorithm
10: Parameterized k-Clustering: The distance matters!
11: Spatial Analysis Made Easy with Linear Regression and Kernels
12: $\ell_1$-sparsity Approximation Bounds for Packing Integer Programs
13: Slightly Superexponential Parameterized Problems
14: Optimal Algorithm to Reconstruct a Tree from a Subtree Distance
15: On Greedy Algorithms for Binary de Bruijn Sequences
16: Faster and simpler algorithms for finding large patterns in permutations
17: Efficient Private Algorithms for Learning Large-Margin Halfspaces
18: Generation of Tree-Child phylogenetic networks
19: Circuit Transformations for Quantum Architectures
20: FPRAS for the Potts Model and the Number of $k$-colorings
21: Succinct Data Structures for Families of Interval Graphs
22: Optimal Distributed Covering Algorithms
23: Adaptive Estimation for Approximate k-Nearest-Neighbor Computations
24: A Unifying Framework for Spectrum-Preserving Graph Sparsification and Coarsening
25: An Automatic Speedup Theorem for Distributed Problems
26: Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
27: Arithmetic Progressions of Length Three in Multiplicative Subgroups of $\mathbb{F}_p$
28: Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies
29: A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems
30: On the extension complexity of scheduling
31: Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams
32: Linearly-growing Reductions of Karp’s 21 NP-complete Problems
33: Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons
34: Reconciliation k-median: Clustering with Non-Polarized Representatives
35: Dispersion of Mobile Robots: The Power of Randomness
36: Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
37: Dimension-independent Sparse Fourier Transform
38: High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
39: Reconfiguration of Connected Graph Partitions
40: Padovan heaps
41: Improved algorithms for Correlation Clustering with local objectives
42: Lower Bounds for Multiplication via Network Coding
43: Probabilistic smallest enclosing ball in high dimensions via subgradient sampling
44: Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
45: Fast Concurrent Data Sketches
46: On the Area Requirements of Planar Straight-Line Orthogonal Drawings of Ternary Trees
47: Ratio-Balanced Maximum Flows
48: Quantum walk inspired algorithm for graph similarity and isomorphism