StringologyTimes

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

1: Group Equality in Adaptive Submodular Maximization
2: Minimum $2$-edge strongly biconnected spanning directed subgraph problem
3: Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
4: Finite-rate sparse quantum codes aplenty
5: Approximate Carath'eodory bounds via Discrepancy Theory
6: Maximum Weight b-Matchings in Random-Order Streams
7: Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems
8: Search by triplet: An efficient local track reconstruction algorithm for parallel architectures
9: Vertex Sparsifiers for Hyperedge Connectivity
10: Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions
11: Determinant Maximization via Matroid Intersection Algorithms
12: Minimum strongly biconnected spanning directed subgraph problem
13: Improved Lower Bounds for Submodular Function Minimization
14: Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
15: Faster Privacy Accounting via Evolving Discretization
16: Closing the Gap Between Directed Hopsets and Shortcut Sets
17: Order-optimal Correlated Rounding for Fulfilling Multi-item E-commerce Orders
18: Parameterized Complexity of Streaming Diameter and Connectivity Problems
19: Killing a Vortex
20: Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
21: Submodular Dominance and Applications
22: Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to k-Median
23: Capacity-Insensitive Algorithms for Online Facility Assignment Problems on a Line
24: Popular Matchings with One-Sided Bias
25: Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
26: On the Complexity of Identifying Strongly Regular Graphs
27: Online Active Regression
28: Caching with Reserves
29: Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs
30: Structured Decompositions: Structural and Algorithmic Compositionality
31: Generalized Wake-Up: Amortized Shared Memory Lower Bounds for Linearizable Data Structures
32: Near-Optimal Bounds for Testing Histogram Distributions
33: Improved Parameterized Complexity of Happy Set Problems
34: Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
35: Kernelization for Graph Packing Problems via Rainbow Matching
36: Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs (Extended version)