StringologyTimes

Data Structures and Algorithms: 2024/2/08-14

1: Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
2: PriorBoost: An Adaptive Algorithm for Learning from Aggregate Responses
3: Scalable Algorithm for Finding Balanced Subgraphs with Tolerance in Signed Networks
4: Low-degree phase transitions for detecting a planted clique in sublinear time
5: Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
6: Tight Approximation Bounds on a Simple Algorithm for Minimum Average Search Time in Trees
7: ShiftDTW: adapting the DTW metric for cyclic time series clustering
8: A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
9: SubGen: Token Generation in Sublinear Time and Memory
10: Rhizomes and Diffusions for Processing Highly Skewed Graphs on Fine-Grain Message-Driven Systems
11: Assortment Planning with Sponsored Products
12: On the Convergence Rate of the Stochastic Gradient Descent (SGD) and application to a modified policy gradient for the Multi Armed Bandit
13: Finding hardness reductions automatically using SAT solvers
14: Quick-Sort Style Approximation Algorithms for Generalizations of Feedback Vertex Set in Tournaments
15: On Differentially Private Subspace Estimation in a Distribution-Free Setting
16: An Exercise in Tournament Design: When Some Matches Must Be Scheduled
17: Value-based Resource Matching with Fairness Criteria: Application to Agricultural Water Trading
18: Learning-augmented Online Algorithm for Two-level Ski-rental Problem
19: A Scalable Algorithm for Individually Fair K-means Clustering
20: Taxonomic classification with maximal exact matches in KATKA kernels and minimizer digests
21: Quantum Speedup for Spectral Approximation of Kronecker Products
22: The $k$-Opt algorithm for the Traveling Salesman Problem has exponential running time for $k \ge 5$
23: Improving LSH via Tensorized Random Projection
24: Simple, unified analysis of Johnson-Lindenstrauss with applications
25: Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
26: The I/O Complexity of Attention, or How Optimal is Flash Attention?
27: On the Distance from Calibration in Sequential Prediction
28: Accelerating Distributed Deep Learning using Lossless Homomorphic Compression
29: Approximating the Maximum Independent Set of Convex Polygons with a Bounded Number of Directions
30: Local Centrality Minimization with Quality Guarantees
31: Pattern Matching with Mismatches and Wildcards
32: Engineering Weighted Connectivity Augmentation Algorithms
33: Insights into $(k,\rho)$-shortcutting algorithms
34: Quantum walks, the discrete wave equation and Chebyshev polynomials
35: On Computationally Efficient Multi-Class Calibration
36: An approximation algorithm for Maximum DiCut vs. Cut
37: Factorizing the Brauer monoid in polynomial time
38: Online Differentially Private Synthetic Data Generation
39: Tight Algorithm for Connected Odd Cycle Transversal Parameterized by Clique-width
40: The Blocklace: A Universal, Byzantine Fault-Tolerant, Conflict-free Replicated Data Type
41: Detecting Low-Degree Truncation
42: An Improved Approximation Algorithm for Metric Triangle Packing
43: Causal Discovery under Off-Target Interventions
44: Integrating High-Dimensional Functions Deterministically
45: Detecting $K_{2,3}$ as an induced minor
46: Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
47: Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems
48: Polynomial-Time Algorithms for Weaver’s Discrepancy Problem in a Dense Regime
49: Sampling Space-Saving Set Sketches
50: Strategizing against No-Regret Learners in First-Price Auctions
51: Almost Tight Bounds for Online Hypergraph Matching
52: Parameterized dynamic data structure for Split Completion
53: Sequence graphs realizations and ambiguity in language models
54: Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs
55: Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity