StringologyTimes

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

1: Lower Bounds for Dynamic Distributed Task Allocation
2: Quantum algorithm for Petz recovery channels and pretty good measurements
3: Sampling from a $k$-DPP without looking at all items
4: Partial Recovery in the Graph Alignment Problem
5: Constructing Basis Path Set by Eliminating Path Dependency
6: A Method for Fast Computing the Algebraic Degree of Boolean Functions
7: Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
8: Adapting $k$-means algorithms for outliers
9: Parallel Planar Subgraph Isomorphism and Vertex Connectivity
10: Approximating Sparse Quadratic Programs
11: Multicommodity Flows in Planar Graphs with Demands on Faces
12: A (Slightly) Improved Approximation Algorithm for Metric TSP
13: Minimizing Convex Functions with Rational Minimizers
14: Finding Densest $k$-Connected Subgraphs
15: On girth and the parameterized complexity of token sliding and token jumping
16: The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
17: b-articulation points and b-bridges in strongly biconnected directed graphs
18: Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
19: New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
20: Efficient Parameter Estimation of Truncated Boolean Product Distributions
21: Solving Packing Problems with Few Small Items Using Rainbow Matchings
22: Optimization from Structured Samples for Coverage Functions
23: Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
24: Faster Graph Embeddings via Coarsening
25: Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches
26: Near-Linear Time Edit Distance for Indel Channels
27: Approximation algorithms for car-sharing problems