StringologyTimes

Data Structures and Algorithms: 2020/8/15-21

1: On the Hardness of Massively Parallel Computation
2: New Techniques for Proving Fine-Grained Average-Case Hardness
3: On Efficient Low Distortion Ultrametric Embedding
4: Finding a Shortest Even Hole in Polynomial Time
5: Selection on $X_1 + X_1 + \cdots X_m$ via Cartesian product tree
6: Probabilistic Skyline Query Processing over Uncertain Data Streams in Edge Computing Environments
7: Algorithm for SIS and MultiSIS problems
8: Approximate Hypergraph Vertex Cover and generalized Tuza’s conjecture
9: On the Sample Complexity of Reinforcement Learning with Policy Space Generalization
10: Grundy Distinguishes Treewidth from Pathwidth
11: A unified algorithm for colouring graphs of bounded clique-width
12: When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fr'echet Distance under Translation
13: Cardinality estimation using Gumbel distribution
14: SF-GRASS: Solver-Free Graph Spectral Sparsification
15: New Quality Metrics for Dynamic Graph Drawing
16: Planar L-Drawings of Bimodal Graphs
17: Minimum Eccentricity Shortest Path Problem with Respect to Structural Parameters
18: Four short stories on surprising algorithmic uses of treewidth
19: Differentially Private Clustering: Tight Approximation Ratios
20: Sampling Multiple Edges Efficiently
21: Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outliers
22: Scalable Blocking for Very Large Databases
23: Parameterized Algorithms for Queue Layouts
24: Disjoint Shortest Paths with Congestion on DAGs
25: Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
26: Competitive Analysis for Two Variants of Online Metric Matching Problem
27: Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
28: Simple Counting and Sampling Algorithms for Graphs with Bounded Pathwidth
29: Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
30: A Simple Deterministic Algorithm for Edge Connectivity
31: The Power of Hashing with Mersenne Primes
32: Non-Mergeable Sketching for Cardinality Estimation
33: DPMC: Weighted Model Counting by Dynamic Programming on Project-Join Trees
34: Faster Heuristics for Graph Burning
35: Solving Problems on Generalized Convex Graphs via Mim-Width
36: On Fine-Grained Exact Computation in Regular Graphs
37: Greedy Approaches to Online Stochastic Matching
38: Optimal algorithm for computing Steiner 3-eccentricities of trees
39: $2$-Layer $k$-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth
40: Schematic Representation of Large Biconnected Graphs
41: Comparison of Algorithms for Simple Stochastic Games (Full Version)