StringologyTimes

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

1: Unbounded Error Correcting Codes
2: On the Complexity of 2-club Cluster Editing with Vertex Splitting
3: Faster feasibility for dynamic flows and transshipments on temporal networks
4: Uniformity testing when you have the source code
5: Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA
6: On the cohesion and separability of average-link for hierarchical agglomerative clustering
7: Average-Distortion Sketching
8: Monotone Submodular Multiway Partition
9: Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications
10: Near-Optimal Dimension Reduction for Facility Location
11: Recursive and iterative approaches to generate rotation Gray codes for stamp foldings and semi-meanders
12: Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint
13: Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
14: On Differentially Private String Distances
15: Weak to Strong Learning from Aggregate Labels
16: Simple approximation algorithms for Polyamorous Scheduling
17: An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
18: One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
19: Parallel Higher-order Truss Decomposition
20: A New 0(klog n) Algorithm for Josephus Problem
21: Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
22: Counterexamples to a Weitz-Style Reduction for Multispin Systems
23: Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
24: Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noise
25: Efficient Classical Computation of Single-Qubit Marginal Measurement Probabilities to Simulate Certain Classes of Quantum Algorithms
26: Phase Transitions via Complex Extensions of Markov Chains
27: Estimating Causal Effects in Partially Directed Parametric Causal Factor Graphs
28: Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
29: Compressed Game Solving
30: An Improved Algorithm for Sparse Instances of SAT
31: Listing 6-Cycles in Sparse Graphs
32: Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees
33: QR Sort: A Novel Non-Comparative Sorting Algorithm
34: Model Stealing for Any Low-Rank Language Model
35: A Simple Algorithm for Dynamic Carpooling with Recourse
36: Elastic-Degenerate String Comparison
37: Pirogov–Sinai Theory Beyond Lattices
38: New Separations and Reductions for Directed Preservers and Hopsets
39: Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
40: Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems
41: Optimal Decentralized Smoothed Online Convex Optimization
42: Theoretical Analysis of Byte-Pair Encoding
43: Tolerant Testing of Stabilizer States with Mixed State Inputs
44: Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity
45: An alignment problem
46: Stochastic Matching via In-n-Out Local Computation Algorithms
47: Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint
48: Non-Euclidean High-Order Smooth Convex Optimization
49: Nearly Tight Bounds on Testing of Metric Properties
50: Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
51: Weak Poincar'e Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses
52: Comparative genomics with succinct colored de Bruijn graphs
53: Efficiently learning and sampling multimodal distributions with data-based initialization
54: FlexFlood: Efficiently Updatable Learned Multi-dimensional Index
55: Parallel $k$d-tree with Batch Updates
56: An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
57: Enhancing Scalability and Performance in Influence Maximization with Optimized Parallel Processing
58: iFlow: An Interactive Max-Flow/Min-Cut Algorithms Visualizer