StringologyTimes

Data Structures and Algorithms: 2023/7/01-07

1: HashMem: PIM-based Hashmap Accelerator
2: An Improved Deterministic Algorithm for the Online Min-Sum Set Cover Problem
3: Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler–Leman
4: Algorithms for Shipping Container Delivery Scheduling
5: Solving Edge Clique Cover Exactly via Synergistic Data Reduction
6: Breaking the Metric Voting Distortion Barrier
7: A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
8: Maximal $k$-Edge-Connected Subgraphs in Almost-Linear Time for Small $k$
9: Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal Sets
10: On Finding Constrained Independent Sets in Cycles
11: Abstract Orientable Incidence Structure and Algorithms for Finite Bounded Acyclic Categories. II. Data Structure and Fundamental Operations
12: Kernelization for Finding Lineal Topologies (Depth-First Spanning Trees) with Many or Few Leaves
13: Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard
14: Moments, Random Walks, and Limits for Spectrum Approximation
15: Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage
16: Massively Parallel Algorithms for the Stochastic Block Model
17: Effective Resistances in Non-Expander Graphs
18: Listing Small Minimal $s,t$-separators in FPT-Delay
19: New Bounds for Time-Dependent Scheduling with Uniform Deterioration
20: What if we tried Less Power? – Lessons from studying the power of choices in hashing-based data structures
21: Rapid mixing of global Markov chains via spectral independence: the unbounded degree case
22: An FTP Algorithm for Temporal Graph Untangling
23: On Symmetric Factorizations of Hankel Matrices
24: Greedy Minimum-Energy Scheduling
25: New Prophet Inequalities via Poissonization and Sharding
26: An embarrassingly parallel optimal-space cardinality estimation algorithm
27: Kernelizing Problems on Planar Graphs in Sublinear Space and Polynomial Time
28: A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth
29: Complexity Dichotomies for the Maximum Weighted Digraph Partition Problem
30: Learning Mixtures of Gaussians Using the DDPM Objective
31: Fitting an ellipsoid to a quadratic number of random points
32: Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
33: A contraction-recursive algorithm for treewidth
34: Polynomial-time Approximation of Independent Set Parameterized by Treewidth
35: Constant-time edge label and leaf pointer maintenance on sliding suffix trees
36: Matrix Multiplication Using Only Addition
37: Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
38: An Optimal Multiple-Class Encoding Scheme for a Graph of Bounded Hadwiger Number
39: Structural and Combinatorial Properties of 2-swap Word Permutation Graphs
40: Improved approximation algorithms for some capacitated $k$ edge connectivity problems
41: Transaction Fee Mechanism Design with Active Block Producers
42: Sparse Graphs of Twin-width 2 Have Bounded Tree-width
43: Threshold Testing and Semi-Online Prophet Inequalities
44: Faster Detours in Undirected Graphs
45: Evaluating Restricted First-Order Counting Properties on Nowhere Dense Classes and Beyond
46: Fast Private Kernel Density Estimation via Locality Sensitive Quantization
47: Linear-time computation of generalized minimal absent words for multiple strings
48: Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
49: Independent Sets in Elimination Graphs with a Submodular Objective
50: Exact and Parameterized Algorithms for the Independent Cutset Problem
51: Improved Approximation for Two-dimensional Vector Multiple Knapsack
52: Directed Poincar'e Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions
53: An Approximation Algorithm for the Exact Matching Problem in Bipartite Graphs
54: Approximate Turing kernelization and lower bounds for domination problems
55: Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
56: Maximum edge colouring problem on graphs that exclude a fixed minor
57: Density-Sensitive Algorithms for $(\Delta + 1)$-Edge Coloring
58: Gaussian Database Alignment and Gaussian Planted Matching
59: The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings
60: The landscape of compressibility measures for two-dimensional data
61: Efficiency of Self-Adjusting Heaps
62: Approximation Algorithms for Directed Weighted Spanners
63: Shortest Beer Path Queries based on Graph Decomposition
64: Finding Favourite Tuples on Data Streams with Provably Few Comparisons
65: A Simple $(1-\epsilon)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
66: Efficient Semiring-Weighted Earley Parsing
67: A Near-Linear Time Algorithm for the Chamfer Distance
68: Optimal Scalarizations for Sublinear Hypervolume Regret
69: QI2 – an Interactive Tool for Data Quality Assurance
70: Differential Privacy for Clustering Under Continual Observation
71: A Multivariate Complexity Analysis of the Generalized Noah’s Ark Problem
72: Improved Algorithms for White-Box Adversarial Streams