StringologyTimes

Data Structures and Algorithms: 2024/12/01-07

1: Quantum algorithm for approximating the expected value of a random-exist quantified oracle
2: A Generalized Trace Reconstruction Problem: Recovering a String of Probabilities
3: Efficient Kernelization Algorithm for Bipartite Graph Matching
4: Data-Driven Solution Portfolios
5: HT-HEDL: High-Throughput Hypothesis Evaluation in Description Logic
6: SPILDL: A Scalable and Parallel Inductive Learner in Description Logic
7: Optimal Algorithms for Augmented Testing of Discrete Distributions
8: Space Complexity of Minimum Cut Problems in Single-Pass Streams
9: Edge-Minimum Walk of Modular Length in Polynomial Time
10: Near-Optimal Resilient Labeling Schemes
11: Nonlinear functions of quantum states
12: You (Almost) Can’t Beat Brute Force for 3-Matroid Intersection
13: Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
14: UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search
15: The Cost of Consistency: Submodular Maximization with Constant Recourse
16: Simple Construction of Greedy Trees and Greedy Permutations
17: The Two-Center Problem of Uncertain Points on Cactus Graphs
18: The Two-Center Problem of Uncertain Points on Trees
19: The Space Complexity of Approximating Logistic Loss
20: Efficient Graph Matching for Correlated Stochastic Block Models
21: The Broader Landscape of Robustness in Algorithmic Statistics
22: Computing the Center of Uncertain Points on Cactus Graphs
23: Improved Differentially Private Continual Observation Using Group Algebra
24: Extracting Dual Solutions via Primal Optimizers
25: Theoretical limitations of multi-layer Transformer
26: Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs
27: Sinkhorn Algorithm for Sequentially Composed Optimal Transports
28: Optimal bounds on a tree inference algorithm
29: Dynamic Consistent $k$-Center Clustering with Optimal Recourse
30: On Approximability of $\ell_2^2$ Min-Sum Clustering
31: Classic Round-Up Variant of Fast Unsigned Division by Constants: Algorithm and Full Proof
32: The Online Submodular Assignment Problem
33: Combinatorial Selection with Costly Information
34: Computing diverse pair of solutions for tractable SAT
35: Recognizing 2-Layer and Outer $k$-Planar Graphs
36: Robust Contraction Decomposition for Minor-Free Graphs and its Applications
37: Towards counterfactual fairness through auxiliary variables
38: Overlay Network Construction: Improved Overall and Node-Wise Message Complexity
39: A Subquadratic Time Approximation Algorithm for Individually Fair k-Center
40: Succinct Data Structures for Segments
41: Integer and Unsplittable Multiflows in Series-Parallel Digraphs
42: Accelerating Proximal Gradient Descent via Silver Stepsizes
43: Sliding Squares in Parallel
44: Multicriteria Spanners – A New Tool for Network Design
45: Convergence analysis of wide shallow neural operators within the framework of Neural Tangent Kernel
46: No-Free-Lunch Theories for Tensor-Network Machine Learning Models