StringologyTimes

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

1: A Query-Optimal Algorithm for Finding Counterfactuals
2: Finding Matching Cuts in $H$-Free Graphs
3: Streaming complexity of CSPs with randomly ordered constraints
4: Exact Flow Sparsification Requires Unbounded Size
5: Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions
6: Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
7: Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
8: A tight quasi-polynomial bound for Global Label Min-Cut
9: Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
10: Fixed-Parameter Tractability of Maximum Colored Path and Beyond
11: Matching Patterns with Variables Under Edit Distance
12: Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
13: Dynamic Algorithms for Maximum Matching Size
14: Improved Algorithms for Recognizing Perfect Graphs and Finding Shortest Odd and Even Holes
15: Approximating Highly Inapproximable Problems on Graphs of Bounded Twin-Width
16: Curve Simplification and Clustering under Fr'echet Distance
17: Adaptive Sketches for Robust Regression with Importance Sampling
18: A Nearly Tight Analysis of Greedy k-means++
19: Online Prediction in Sub-linear Space
20: Approximation algorithms for Steiner Tree Augmentation Problems
21: Parallel Best Arm Identification in Heterogeneous Environments
22: Streaming Algorithms with Large Approximation Factors
23: On the Practical Power of Automata in Pattern Matching
24: Online Lewis Weight Sampling
25: Shrunk subspaces via operator Sinkhorn iteration
26: Concurrent Composition Theorems for Differential Privacy
27: Extracting Densest Sub-hypergraph with Convex Edge-weight Functions
28: Online Total Completion Time Scheduling on Parallel Identical Machines
29: A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
30: A quadratic-order problem kernel for the traveling salesman problem parameterized by the vertex cover number
31: Streaming Algorithms for Support-Aware Histograms
32: Almost Tight Bounds for Online Facility Location in the Random-Order Model
33: Quantum tomography using state-preparation unitaries
34: Robust Factorizations and Colorings of Tensor Graphs
35: Recursive McCormick Linearization of Multilinear Programs
36: Bernoulli Factories for Flow-Based Polytopes
37: Accelerating Frank-Wolfe Algorithm using Low-Dimensional and Adaptive Data Structures
38: PackCache: An Online Cost-driven Data Caching Algorithm in the Cloud
39: Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling
40: Solving the unit-load pre-marshalling problem in block stacking storage systems with multiple access directions
41: Subsequences in Bounded Ranges: Matching and Analysis Problems
42: Efficient Constructions for the Gy\H{o}ri-Lov'{a}sz Theorem on Almost Chordal Graphs
43: Towards An Optimal Solution to Place Bistatic Radars for Belt Barrier Coverage with Minimum Cost
44: On Regularity Lemma and Barriers in Streaming and Dynamic Matching
45: A Near-Linear Time Sampler for the Ising Model with External Field
46: Composition Theorems for Interactive Differential Privacy
47: Regret Minimization with Noisy Observations
48: Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme
49: New Auction Algorithms for Path Planning, Network Transport, and Reinforcement Learning
50: Exact Matching: Correct Parity and FPT Parameterized by Independence Number
51: Computing Densest $k$-Subgraph with Structural Parameters
52: Computing Tree Decompositions with Small Independence Number
53: Short-Depth Circuits for Dicke State Preparation
54: Differentially Private Partial Set Cover with Applications to Facility Location
55: The Two-Stripe Symmetric Circulant TSP is in P