StringologyTimes

Data Structures and Algorithms: 2019/11/15-21

1: In Search of the Fastest Concurrent Union-Find Algorithm
2: Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles
3: Graph Iso/Auto-morphism: A Divide-&-Conquer Approach
4: Computationally Data-Independent Memory Hard Functions
5: Non-Monotone Submodular Maximization with Multiple Knapsacks in Static and Dynamic Settings
6: New Query Lower Bounds for Submodular Function MInimization
7: Delta-stepping SSSP: from Vertices and Edges to GraphBLAS Implementations
8: Strategy-Stealing is Non-Constructive
9: Approximating the Distance to Monotonicity of Boolean Functions
10: Memory-Efficient Performance Monitoring on Programmable Switches with Lean Algorithms
11: Regularized Weighted Low Rank Approximation
12: Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time
13: Counting solutions to random CNF formulas
14: Corrfunc: Blazing fast correlation functions with AVX512F SIMD Intrinsics
15: Faster Integer Multiplication Using Preprocessing
16: A one-phase tree-based algorithm for mining high-utility itemsets from a transaction database
17: Sparse Hopsets in Congested Clique
18: A New Approximation Algorithm for the Minimum 2-Edge-Connected Spanning Subgraph Problem
19: Approximation of Steiner Forest via the Bidirected Cut Relaxation
20: Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
21: Testing Properties of Multiple Distributions with Few Samples
22: Robust Algorithms for the Secretary Problem
23: Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning
24: Top-down induction of decision trees: rigorous guarantees and inherent limitations
25: Finding Skewed Subcubes Under a Distribution
26: Algorithmic Discrepancy Minimization
27: Implicit Enumeration of Topological-Minor-Embeddings and Its Application to Planar Subgraph Enumeration
28: Optimal Single-Choice Prophet Inequalities from Samples
29: Learning-Assisted Competitive Algorithms for Peak-Aware Energy Scheduling
30: Estimating Entropy of Distributions in Constant Space
31: Consistent recovery threshold of hidden nearest neighbor graphs
32: Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers
33: Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
34: Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering
35: Topological computing of arrangements with (co)chains
36: Property Testing of LP-Type Problems
37: The Power of Factorization Mechanisms in Local and Central Differential Privacy
38: Improved Compressed String Dictionaries
39: Concurrent Expandable AMQs on the Basis of Quotient Filters
40: Extending General Compact Querieable Representations to GIS Applications
41: Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
42: Steepest ascent can be exponential in bounded treewidth problems
43: Corruption-robust exploration in episodic reinforcement learning
44: Online Spectral Approximation in Random Order Streams
45: Frequent Elements with Witnesses in Data Streams
46: Geometric Planar Networks on Bichromatic Points
47: Towards a Theory of Parameterized Streaming Algorithms
48: Exact and approximation algorithms for the expanding search problem
49: New Algorithms for Mixed Dominating Set
50: Faster Dynamic Compressed d-ary Relations
51: New structures to solve aggregated queries for trips over public transportation networks
52: Grammar Compressed Sequences with Rank/Select Support
53: Synthesis of Reduced Asymmetric Choice Petri Nets
54: Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs
55: The Karger-Stein Algorithm is Optimal for $k$-cut
56: Lower Bounds for Function Inversion with Quantum Advice
57: A 2-approximation for the $k$-prize-collecting Steiner tree problem
58: Energy consumption in compact integer vectors: A study case
59: S-RASTER: Contraction Clustering for Evolving Data Streams
60: Navigating Planar Topologies in Near-Optimal Space and Time