StringologyTimes

Data Structures and Algorithms: 2018/5/08-14

1: Dichotomy Results for Classified Rank-Maximal Matchings and Popular Matchings
2: Finding Frequent Entities in Continuous Data
3: Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
4: Parallel Graph Connectivity in Log Diameter Rounds
5: Round-Hashing for Data Storage: Distributed Servers and External-Memory Tables
6: Fair Allocation of Indivisible Public Goods
7: The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
8: Optimally Sorting Evolving Data
9: Characterizing and decomposing classes of threshold, split, and bipartite graphs via 1-Sperner hypergraphs
10: Exact Lexicographic Scheduling and Approximate Rescheduling
11: Tight bounds for undirected graph exploration with pebbles and multiple agents
12: Deterministically Maintaining a $(2+\epsilon)$-Approximate Minimum Vertex Cover in $O(1/\epsilon^2)$ Amortized Update Time
13: Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
14: Robust-to-Dynamics Optimization
15: New Bounds on Augmenting Steps of Block-structured Integer Programs
16: Near Optimal Linear Algebra in the Online and Sliding Window Models
17: Haplotype-aware graph indexes
18: The Energy Complexity of Diameter and Minimum Cut Computation in Bounded-Genus Networks
19: A 1.5-Approximation for Path TSP
20: Beating Fredman-Koml'{o}s for perfect $k$-hashing
21: Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs
22: Erasure Correction for Noisy Radio Networks
23: An $O(N)$ Sorting Algorithm: Machine Learning Sort
24: On the Parameterized Complexity of Graph Modification to First-Order Logic Properties
25: Breaking the Scalability Barrier of Causal Broadcast for Large and Dynamic Systems
26: Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity
27: Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs
28: A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
29: Peres-Style Recursive Algorithms
30: Do Outliers Ruin Collaboration?
31: New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms
32: Lock-Free Search Data Structures: Throughput Modelling with Poisson Processes
33: Algorithms and Complexity of Range Clustering
34: Prophets and Secretaries with Overbooking
35: Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable