StringologyTimes

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

1: Arc-Flags Meet Trip-Based Public Transit Routing
2: Compressibility-Aware Quantum Algorithms on Strings
3: Interpolation Learning With Minimum Description Length
4: Bandit Social Learning: Exploration under Myopic Behavior
5: Dual Graph Multitask Framework for Imbalanced Delivery Time Estimation
6: LP-Duality Theory and the Cores of Games
7: Dynamic Flows with Time-Dependent Capacities
8: Forbidden Patterns in Temporal Graphs Resulting from Encounters in a Corridor
9: Fully dynamic clustering and diversity maximization in doubling metrics
10: An Efficient B-tree Implementation for Memory-Constrained Embedded Systems
11: Perfect Sampling of $q$-Spin Systems on $\mathbb Z^2$ via Weak Spatial Mixing
12: Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
13: Maximum Independent Set when excluding an induced minor: $K_1 + tK_2$ and $tC_3 \uplus C_4$
14: Sample-Based Online Generalized Assignment Problem with Unknown Poisson Arrivals
15: Incremental $(1-\epsilon)$-approximate dynamic matching in $O(poly(1/\epsilon))$ update time
16: The Scope of Multicalibration: Characterizing Multicalibration via Property Elicitation
17: Subsampling Suffices for Adaptive Data Analysis
18: Query-Centered Temporal Community Search via Time-Constrained Personalized PageRank
19: Realizing temporal graphs from fastest travel times
20: Partitioning the Bags of a Tree Decomposition Into Cliques
21: Uniformity Testing over Hypergrids with Subcube Conditioning
22: Characterizations of Network Auctions and Generalizations of VCG
23: Faster Wavelet Tree Queries
24: SAT Requires Exhaustive Search
25: Parameterized Max Min Feedback Vertex Set
26: On Existence of Must-Include Paths and Cycles in Undirected Graphs
27: Communication-Efficient Distributed Graph Clustering and Sparsification under Duplication Models
28: Classification via two-way comparisons
29: Fully Dynamic $k$-Center in Low Dimensions via Approximate Furthest Neighbors
30: Adaptive control of dynamic networks
31: Fast Algorithms via Dynamic-Oracle Matroids
32: The Continuous-Time Joint Replenishment Problem: $\epsilon$-Optimal Policies via Pairwise Alignment
33: A Vectorised Packing Algorithm for Efficient Generation of Custom Traffic Matrices
34: DenseQMC: an efficient bit-slice implementation of the Quine-McCluskey algorithm
35: Basic quantum subroutines: finding multiple marked elements and summing numbers
36: Faster high-accuracy log-concave sampling via algorithmic warm starts
37: Replicable Clustering
38: Dynamic Euclidean Bottleneck Matching
39: Approximating Bin Packing with Conflict Graphs via Maximization Techniques
40: Lightweight-Yet-Efficient: Revitalizing Ball-Tree for Point-to-Hyperplane Nearest Neighbor Search
41: New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
42: Snakes and Ladders: a Treewidth Story