StringologyTimes

Data Structures and Algorithms: 2022/9/15-21

1: Parameterized algorithms for node connectivity augmentation problems
2: Multiway Powersort
3: Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
4: Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
5: Concurrent Size
6: Multicalibrated Regression for Downstream Fairness
7: Envy-freeness in 3D Hedonic Games
8: Omnipredictors for Constrained Optimization
9: On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
10: $\tilde{O}(n+\mathrm{poly}(k))$-time Algorithm for Bounded Tree Edit Distance
11: Exploring the Tradeoff between Competitive Ratio and Variance in Online-Matching Markets
12: On Weighted Graph Sparsification by Linear Sketching
13: $b$-Coloring Parameterized by Pathwidth is XNLP-complete
14: A $(1.5+\epsilon)$-Approximation Algorithm for Weighted Connectivity Augmentation
15: Prophet Inequalities for Cost Minimization
16: Fast approximation of search trees on trees with centroid trees
17: Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting
18: The trace reconstruction problem for spider graphs
19: Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation
20: Exact Matching and the Top-k Perfect Matching Problem
21: A Nearly Tight Lower Bound for the $d$-Dimensional Cow-Path Problem
22: GenPIP: In-Memory Acceleration of Genome Analysis via Tight Integration of Basecalling and Read Mapping
23: Online and semi-online scheduling on two hierarchical machines with a common due date to maximize the total early work
24: Faster Randomized Interior Point Methods for Tall/Wide Linear Programs
25: Parameterized Complexity of Path Set Packing
26: An Optimal Level-synchronous Shared-memory Parallel BFS Algorithm with Optimal parallel Prefix-sum Algorithm and its Implications for Energy Consumption
27: A Simple Framework for Finding Balanced Sparse Cuts via APSP
28: Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
29: Convergence of the number of period sets in strings
30: Gradual Weisfeiler-Leman: Slow and Steady Wins the Race
31: Rounds vs Communication Tradeoffs for Maximal Independent Sets
32: Cache-Oblivious Representation of B-Tree Structures
33: MARIA: Multiple-alignment $r$-index with aggregation
34: Natural Wave Numbers, Natural Wave Co-numbers, and the Computation of the Primes
35: Data Structures for Topologically Sound Higher-Dimensional Diagram Rewriting
36: Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
37: Development of a Parallel BAT and Its Applications in Binary-state Network Reliability Problems
38: Parametric Synthesis of Computational Circuits for Complex Quantum Algorithms
39: Algorithms for Large-scale Network Analysis and the NetworKit Toolkit
40: Modeling the Small-World Phenomenon with Road Networks
41: On the Correlation Gap of Matroids
42: Exact and sampling methods for mining higher-order motifs in large hypergraphs
43: On Reachable Assignments under Dichotomous Preferences
44: Improved Approximation for Two-Edge-Connectivity
45: Avoid One’s Doom: Finding Cliff-Edge Configurations in Petri Nets
46: Characterizing the Decidability of Finite State Automata Team Games with Communication