StringologyTimes

Data Structures and Algorithms: 2022/4/08-14

1: Output-sensitive ERM-based techniques for data-driven algorithm design
2: Testing Positive Semidefiniteness Using Linear Measurements
3: High-Dimensional Geometric Streaming in Polynomial Space
4: Matrix multiplication via matrix groups
5: Deterministic, Near-Linear $\varepsilon$-Approximation Algorithm for Geometric Bipartite Matching
6: The Power of Filling in Balanced Allocations
7: Ranking with submodular functions on a budget
8: The Complexity of Infinite-Horizon General-Sum Stochastic Games
9: Learning Polynomial Transformations
10: An Improved Integer Modular Multiplicative Inverse (modulo $2^w$)
11: Reduction ratio of the IS-algorithm: worst and random cases
12: A BAT-based Exact-Solution Algorithm for the Series-Parallel Redundancy Allocation Problem with Mixed Components
13: Faster Min-Plus Product for Monotone Instances
14: Testability in group theory
15: Efficient Reconstruction of Stochastic Pedigrees: Some Steps From Theory to Practice
16: EPTAS for the dual of splittable bin packing with cardinality constraint
17: Improved Weighted Matching in the Sliding Window Model
18: Minimal Roman Dominating Functions: Extensions and Enumeration
19: Improved Approximations for Euclidean $k$-means and $k$-median, via Nested Quasi-Independent Sets
20: The Complexity of Temporal Vertex Cover in Small-Degree Graphs
21: On complex roots of the independence polynomial
22: Constrained Shortest Path and Hierarchical Structures
23: Schwartz-Zippel for multilinear polynomials mod N
24: Submodular Maximization Subject to Matroid Intersection on the Fly
25: Computing a Sparse Projection into a Box
26: Galactic Token Sliding
27: Linearly ordered colourings of hypergraphs
28: On Top-$k$ Selection from $m$-wise Partial Rankings via Borda Counting
29: 1-Extendability of independent sets
30: Computing $k$-Bisimulations for Large Graphs: A Comparison and Efficiency Analysis
31: Iterative Hard Thresholding with Adaptive Regularization: Sparser Solutions Without Sacrificing Runtime
32: Undirected $(1+\varepsilon)$-Shortest Paths via Minor-Aggregates: Near-Optimal Deterministic Parallel & Distributed Algorithms
33: Efficient Construction of the BWT for Repetitive Text Using String Compression
34: PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
35: A branch and bound technique for finding the minimal solutions of the linear optimization problems subjected to Lukasiewicz
36: Distributed Coalgebraic Partition Refinement
37: Linear Programs with Polynomial Coefficients and Applications to 1D Cellular Automata
38: Sketching Algorithms and Lower Bounds for Ridge Regression
39: A Fixed-Parameter Algorithm for the Kneser Problem
40: (Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
41: Better-Than-$\frac{4}{3}$-Approximations for Leaf-to-Leaf Tree and Connectivity Augmentation