StringologyTimes

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

1: Performance of $\ell_1$ Regularization for Sparse Convex Optimization
2: A simple deterministic near-linear time approximation scheme for transshipment with arbitrary positive edge costs
3: Differentially Private Clustering in Data Streams
4: Tur'{a}n’s Theorem Through Algorithmic Lens
5: Diverse Approximations for Monotone Submodular Maximization Problems with a Matroid Constraint
6: Decomposition Based Refinement for the Network Interdiction Problem
7: On Diameter Approximation in Directed Graphs
8: Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes
9: Zip-zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent
10: Computing SEQ-IC-LCS of Labeled Graphs
11: Sandpile Prediction on Undirected Graphs
12: Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
13: WSRPT is 1.2259-competitive for Weighted Completion Time Scheduling
14: Lower Bounds for Matroid Optimization Problems with a Linear Constraint
15: The Impact of Space-Filling Curves on Data Movement in Parallel Systems
16: Fully Scalable MPC Algorithms for Clustering in High Dimension
17: New Bounds for Matrix Multiplication: from Alpha to Omega
18: Faster Approximation Scheme for Euclidean $k$-TSP
19: Sampling Proper Colorings on Line Graphs Using $(1+o(1))\Delta$ Colors
20: Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
21: Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
22: Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems
23: Lipschitz Continuous Algorithms for Covering Problems
24: Extending the primal-dual 2-approximation algorithm beyond uncrossable set families
25: IterLara: A Turing Complete Algebra for Big Data, AI, Scientific Computing, and Database
26: Quantum Graph Drawing
27: Maximum Flows in Parametric Graph Templates
28: Fast Algorithms for Energy Games in Special Cases
29: Santa Claus meets Makespan and Matroids: Algorithms and Reductions
30: Approximation Algorithms for the Graph Burning on Cactus and Directed Trees
31: Splitting-off in Hypergraphs
32: Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs
33: Fully Dynamic Matching: $(2-\sqrt{2})$-Approximation in Polylog Update Time
34: Resource Augmentation Analysis of the Greedy Algorithm for the Online Transportation Problem
35: Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
36: Quantum Tutte Embeddings
37: Fixed-Parameter Algorithms for Fair Hitting Set Problems
38: The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations
39: Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond
40: Scalable Auction Algorithms for Bipartite Maximum Matching Problems
41: Cut Sparsification and Succinct Representation of Submodular Hypergraphs
42: Minimum Target Sets in Non-Progressive Threshold Models: When Timing Matters
43: Fast 2-Approximate All-Pairs Shortest Paths
44: Dynamic Planar Embedding is in DynFO
45: Submodular Maximization under the Intersection of Matroid and Knapsack Constraints
46: The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
47: $\mathcal{P}$-matchings Parameterized by Treewidth
48: The Role of Dimension in the Online Chasing Problem
49: Solving Knapsack with Small Items via L0-Proximity
50: Approximately counting independent sets in dense bipartite graphs via subspace enumeration
51: LinearSankoff: Linear-time Simultaneous Folding and Alignment of RNA Homologs
52: Group Testing in Arbitrary Hypergraphs and Related Combinatorial Structures
53: On the Tractability of Defensive Alliance Problem
54: On Dynamic Graph Algorithms with Predictions
55: Labeling Methods for Partially Ordered Paths
56: Online Algorithms and Lower Bounds for Average-Case Matrix Discrepancy
57: Percolation on hypergraphs and the hard-core model
58: Dynamic constant time parallel graph algorithms with sub-linear work
59: On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages
60: Stop Simulating! Efficient Computation of Tournament Winning Probabilities
61: Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses
62: Fast Approximate Nearest Neighbor Search with a Dynamic Exploration Graph using Continuous Refinement
63: Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs
64: Efficient algorithms for enumerating maximal common subsequences of two strings
65: Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
66: Computing a Subtrajectory Cluster from c-packed Trajectories
67: Mutual-visibility in distance-hereditary graphs: a linear-time algorithm
68: A parameterized approximation scheme for the 2D-Knapsack problem with wide items
69: Shortest Dominating Set Reconfiguration under Token Sliding
70: Ellipsoid fitting up to constant via empirical covariance estimation
71: Hypergraph Diffusions and Resolvents for Norm-Based Hypergraph Laplacians
72: Out-of-Order Sliding-Window Aggregation with Efficient Bulk Evictions and Insertions (Extended Version)
73: Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
74: Epsilon(star): Privacy Metric for Machine Learning Models
75: A Fair and Memory/Time-efficient Hashmap
76: A Generalized Quantum Branching Program
77: Subset Sampling and Its Extensions