StringologyTimes

Data Structures and Algorithms: 2022/6/15-21

1: The Maximum Linear Arrangement Problem for trees under projectivity and planarity
2: The Complexity of Finding Fair Many-to-One Matchings
3: Sequential Optimization Numbers and Conjecture about Edge-Symmetry and Weight-Symmetry Shortest Weight-Constrained Path
4: On Approximating Total Variation Distance
5: Brownian Noise Reduction: Maximizing Privacy Subject to Accuracy Constraints
6: Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes
7: Faster Decomposition of Weighted Graphs into Cliques using Fisher’s Inequality
8: Balanced Allocations with the Choice of Noise
9: On the fast convergence of minibatch heavy ball momentum
10: Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds
11: Sublinear Algorithms for Hierarchical Clustering
12: Statistical and Computational Phase Transitions in Group Testing
13: Reconstructing Ultrametric Trees from Noisy Experiments
14: Metric-Fair Classifier Derandomization
15: Generalization Bounds for Data-Driven Numerical Linear Algebra
16: Generalized Leverage Scores: Geometric Interpretation and Applications
17: Approximating optimization problems in graphs with locational uncertainty
18: Twin-width and types
19: An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
20: Active Fairness Auditing
21: Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations
22: RECAPP: Crafting a More Efficient Catalyst for Convex Optimization
23: On Computing Optimal Linear Diagrams
24: Scalable Differentially Private Clustering via Hierarchically Separated Trees
25: A remark on Kashin’s discrepancy argument and partial coloring in the Koml'{o}s conjecture
26: Interior point methods are not worse than Simplex
27: Popular decision tree algorithms are provably noise tolerant
28: Learning a Single Neuron with Adversarial Label Noise via Gradient Descent
29: Towards Consensus: Reducing Polarization by Perturbing Social Networks
30: Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm
31: Quantum implementation of circulant matrices and its use in quantum string processing
32: Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk
33: Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models
34: List Colouring Trees in Logarithmic Space
35: Finding $k$-Secluded Trees Faster
36: SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compression
37: Superiority of Instantaneous Decisions in Thin Dynamic Matching Markets
38: Algorithmic Gaussianization through Sketching: Converting Data into Sub-gaussian Random Designs
39: The Complexity of the Co-Occurrence Problem