StringologyTimes

Data Structures and Algorithms: 2021/6/08-14

1: Deterministic Iteratively Built KD-Tree with KNN Search for Exact Applications
2: Parallel Batch-Dynamic Algorithms for $k$-Core Decomposition and Related Graph Problems
3: A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
4: Near-Optimal Dispersion on Arbitrary Anonymous Graphs
5: Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
6: Online Algorithms for Network Robustness under Connectivity Constraints
7: Entropic Independence I: Modified Log-Sobolev Inequalities for Fractionally Log-Concave Distributions and High-Temperature Ising Models
8: Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
9: FPT Algorithms to Compute the Elimination Distance to Bipartite Graphs and More
10: Improved Online Correlated Selection
11: Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead
12: Coresets for Classification – Simplified and Strengthened
13: Sketch-Based Anomaly Detection in Streaming Graphs
14: New Competitive Semi-online Scheduling Algorithms for Small Number of Identical Machines
15: A Quantum Advantage for a Natural Streaming Problem
16: Pricing Ordered Items
17: Boolean Matrix Factorization via Nonnegative Auxiliary Optimization
18: ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain
19: Submodular + Concave
20: Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
21: Strongly Sublinear Algorithms for Testing Pattern Freeness
22: Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
23: Incremental space-filling design based on coverings and spacings: improving upon low discrepancy sequences
24: Pattern-defeating Quicksort
25: Prior-Aware Distribution Estimation for Differential Privacy
26: Local Algorithms for Finding Densely Connected Clusters
27: A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center
28: Fair Disaster Containment via Graph-Cut Problems
29: Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions
30: Deterministic Mincut in Almost-Linear Time
31: Multiway Online Correlated Selection
32: Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time
33: Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model
34: Valued Authorization Policy Existence Problem: Theory and Experiments
35: Classical algorithms and quantum limitations for maximum cut on high-girth graphs
36: Graph Balancing with Orientation Costs
37: An Optimal Algorithm for Strict Circular Seriation
38: Integer programs with bounded subdeterminants and two nonzeros per row
39: Fair Classification with Adversarial Perturbations
40: Small space and streaming pattern matching with k edits
41: Matching Patterns with Variables under Hamming Distance
42: The Complexity of Sparse Tensor PCA
43: Differentially Private Algorithms for Clustering with Stability Assumptions
44: Property-Preserving Hash Functions from Standard Assumptions
45: ExtendedHyperLogLog: Analysis of a new Cardinality Estimator
46: COSTA: Communication-Optimal Shuffle and Transpose Algorithm with Process Relabeling
47: Tight FPT Approximation for Socially Fair Clustering
48: Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes
49: An efficient way to manage ranges of data with Wise Red-Black Trees
50: The k-mappability problem revisited
51: Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
52: Multi-Resource List Scheduling of Moldable Parallel Jobs under Precedence Constraints
53: Semi-verified PAC Learning from the Crowd
54: The Power of Randomization: Efficient and Effective Algorithms for Constrained Submodular Maximization
55: Fast Construction of 4-Additive Spanners
56: Iterative Methods for Private Synthetic Data: Unifying Framework and New Methods
57: Optimal transport in multilayer networks for traffic flow optimization
58: Fair Clustering Under a Bounded Cost
59: Maximin Shares Under Cardinality Constraints
60: Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space
61: Exact Counting and Sampling of Optima for the Knapsack Problem