StringologyTimes

Data Structures and Algorithms: 2020/7/22-28

1: Static and Streaming Data Structures for Fr'echet Distance Queries
2: Interactive Inference under Information Constraints
3: Improved lower and upper bounds on the tile complexity of uniquely self-assembling a thin rectangle non-cooperatively in 3D
4: New Data Structures for Orthogonal Range Reporting and Range Minima Queries
5: Sum-of-squares chordal decomposition of polynomial matrix inequalities
6: Approximate Covering with Lower and Upper Bounds via LP Rounding
7: Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time
8: Adaptive Bin Packing with Overflow
9: An Improved Approximation Algorithm for the Matching Augmentation Problem
10: Space-Efficient Graph Kernelizations
11: R(star)-Grove: Balanced Spatial Partitioning for Large-scale Datasets
12: FPT Approximation for Constrained Metric $k$-Median/Means
13: Two-way Greedy: Algorithms for Imperfect Rationality
14: Total Domination in Unit Disk Graphs
15: Detecting and Enumerating Small Induced Subgraphs in $c$-Closed Graphs
16: Efficient and near-optimal algorithms for sampling small connected subgraphs
17: The Asymmetric Travelling Salesman Problem in Sparse Digraphs
18: Computing nearest neighbour interchange distances between ranked phylogenetic trees
19: Tight Distributed Sketching Lower Bound for Connectivity
20: Improved approximation schemes for early work scheduling on identical parallel machines with common due date
21: Using a geometric lens to find k disjoint shortest paths
22: Tromino Tilings with Pegs via Flow Networks
23: MurTree: Optimal Classification Trees via Dynamic Programming and Search
24: Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions
25: Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
26: From Boltzmann Machines to Neural Networks and Back Again
27: Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model
28: Bounding the trace function of a hypergraph with applications
29: Efficient Approximation Schemes for Stochastic Probing and Prophet Problems
30: Resource Augmentation
31: Distributional Analysis
32: Beyond the Worst-Case Analysis of Algorithms (Introduction)
33: Optimal construction of a layer-ordered heap
34: Improved 3-pass Algorithm for Counting 4-cycles in Arbitrary Order Streaming
35: Internal Quasiperiod Queries
36: The Complexity of the Distributed Constraint Satisfaction Problem
37: New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
38: Learning discrete distributions: user vs item-level privacy
39: Symmetries: From Proofs To Algorithms And Back
40: Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)
41: Counting Short Vector Pairs by Inner Product and Relations to the Permanent
42: Rectangle Tiling Binary Arrays
43: Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow
44: Twin-width III: Max Independent Set, Min Dominating Set, and Coloring
45: Close relatives of Feedback Vertex Set without single-exponential algorithms parameterized by treewidth
46: Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
47: The Complexity of the Partition Coloring Problem