StringologyTimes

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

1: Clustering to Minimize Cluster-Aware Norm Objectives
2: Convex optimization with $p$-norm oracles
3: Testing and learning structured quantum Hamiltonians
4: Embedding Planar Graphs into Graphs of Treewidth $O(\log^{3} n)$
5: Certified binary search tree on W-types
6: Dynamic Accountable Storage: An Efficient Protocol for Real-time Cloud Storage Auditing
7: Perfect Matchings and Popularity in the Many-to-Many Setting
8: An Implementation and Experimental Comparison of Dynamic Ordered Sets
9: Relax and Merge: A Simple Yet Effective Framework for Solving Fair $k$-Means and $k$-sparse Wasserstein Barycenter Problems
10: Prophet Secretary and Matching: the Significance of the Largest Item
11: CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores
12: Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
13: Computing Experiment-Constrained D-Optimal Designs
14: The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner
15: Some easy optimization problems have the overlap-gap property
16: An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
17: Optimality of Frequency Moment Estimation
18: Sample-Efficient Private Learning of Mixtures of Gaussians
19: A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
20: Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
21: Sensitivity Lower Bounds for Approximaiton Algorithms
22: Sampling permutations satisfying constraints within the lopsided local lemma regime
23: Fast, robust approximate message passing
24: Practical, optimal preparation of general quantum state with exponentially improved robustness
25: Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
26: Max-Distance Sparsification for Diversification and Clustering
27: Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
28: Counting random $k$-SAT near the satisfiability threshold
29: Top-k Stabbing Interval Queries
30: Multi-dimensional Approximate Counting
31: On Differentially Private Linear Algebra
32: Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
33: Reconstructing edge-deleted unicyclic graphs
34: Tight Sampling Bounds for Eigenvalue Approximation
35: Discovering Data Structures: Nearest Neighbor Search and Beyond
36: Error Interference in Quantum Simulation
37: Concurrent Composition for Differentially Private Continual Mechanisms
38: Six Candidates Suffice to Win a Voter Majority
39: A refined graph container lemma and applications to the hard-core model on bipartite expanders
40: Rapid Mixing at the Uniqueness Threshold
41: Redundancy Is All You Need
42: Learning Constant-Depth Circuits in Malicious Noise Models
43: Optimal prefix-suffix queries with applications
44: Safe Paths and Sequences for Scalable ILPs in RNA Transcript Assembly Problems
45: $k$NN Attention Demystified: A Theoretical Exploration for Scalable Transformers
46: A unified approach to quantum de Finetti theorems and SoS rounding via geometric quantization
47: On the (Classical and Quantum) Fine-Grained Complexity of Log-Approximate CVP and Max-Cut
48: Scalable DP-SGD: Shuffling vs. Poisson Subsampling
49: Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators
50: Fully Dynamic (\Delta+1) Coloring Against Adaptive Adversaries
51: Mixing time of quantum Gibbs sampling for random sparse Hamiltonians
52: A Generalisation of Voter Model: Influential Nodes and Convergence Properties
53: Approximate counting of permutation patterns