StringologyTimes

Data Structures and Algorithms: 2018/2/15-21

1: Efficient Exact Paths For Dyck and semi-Dyck Labeled Path Reachability
2: Strongly connected components-Algorithm for finding the strongly connected components of a graph
3: Competitive caching with machine learned advice
4: Smooth heaps and a dual view of self-adjusting data structures
5: Grammar-based Compression of Unranked Trees
6: Finding small-width connected path decompositions in polynomial time
7: Fine-Grained Complexity of Safety Verification
8: Distributed coloring in sparse graphs with fewer colors
9: An $O(1)$-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity
10: List Heaps
11: A Faster FPTAS for #Knapsack
12: Minimal Algorithmic Information Loss Methods for Dimension Reduction, Feature Selection and Network Sparsification
13: A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
14: A Reallocation Algorithm for Online Split Packing of Circles
15: Parallel Tempering for the planted clique problem
16: Assigning times to minimise reachability in temporal graphs
17: Refining the $r$-index
18: Parameterized Algorithms for Zero Extension and Metric Labelling Problems
19: Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr"oder paths
20: Online Continuous Submodular Maximization
21: Any-k: Anytime Top-k Tree Pattern Retrieval in Labeled Graphs
22: A Centrality Measure for Cycles and Subgraphs II
23: Approximate Set Union Via Approximate Randomization
24: Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization
25: Lower Bounds on Sparse Spanners, Emulators, and Diameter-reducing shortcuts
26: Faster Algorithms for Integer Programs with Block Structure
27: Minimum length RNA folding trajectories
28: On Finding Dense Common Subgraphs
29: Linear-Time Algorithm for Long LCF with $k$ Mismatches
30: Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms
31: An Efficient Local Search for the Minimum Independent Dominating Set Problem
32: Reconfiguration of Colorable Sets in Classes of Perfect Graphs
33: Discrepancy Analysis of a New Randomized Diffusion Algorithm
34: Upper and lower bounds for dynamic data structures on strings
35: A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts
36: Maximal Exploration of Trees with Energy-Constrained Agents
37: A Simple Parallel and Distributed Sampling Technique: Local Glauber Dynamics
38: On Local Distributed Sampling and Counting
39: An Adaptive Version of Brandes’ Algorithm for Betweenness Centrality
40: Two Algorithms to Compute Symmetry Groups for Landau-Ginzburg Models
41: Distributed Recoloring
42: Breaking the Linear-Memory Barrier in MPC: Fast MIS on Trees with Strongly Sublinear Memory
43: Population Protocols Are Fast
44: Communication-Optimal Convolutional Neural Nets
45: Comparison Based Learning from Weak Oracles
46: Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors)
47: Sublinear Algorithms for MAXCUT and Correlation Clustering
48: Selection from heaps, row-sorted matrices and $X+Y$ using soft heaps
49: Robust Maximization of Non-Submodular Objectives
50: Relative Worst-Order Analysis: A Survey
51: The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments
52: Do Less, Get More: Streaming Submodular Maximization with Subsampling
53: The Cut and Dominating Set Problem in A Steganographer Network
54: ILP-based Local Search for Graph Partitioning
55: The parameterized complexity of finding a 2-sphere in a simplicial complex
56: Wireless Expanders
57: Distributed Symmetry-Breaking Algorithms for Congested Cliques
58: Actively Avoiding Nonsense in Generative Models
59: On the Connection Between Learning Two-Layers Neural Networks and Tensor Decomposition
60: Periodicity in Data Streams with Wildcards
61: Generic Coreset for Scalable Learning of Monotonic Kernels: Logistic Regression, Sigmoid and more
62: Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time
63: Max-size popular matchings and extensions
64: Scaling-up Split-Merge MCMC with Locality Sensitive Sampling (LSS)
65: Spectrally approximating large graphs with smaller graphs
66: A framework for cost-constrained genome rearrangement under Double Cut and Join
67: Randomized sliding window algorithms for regular languages