StringologyTimes

Data Structures and Algorithms: 2020/11/22-28

1: Erd"{o}s-Szekeres Partitioning Problem
2: Improved Dynamic Algorithms for Longest Increasing Subsequence
3: Applying Multi-armed Bandit Algorithms to Computational Advertising
4: Online Maximum $k$-Interval Coverage Problem
5: Harmonic Algorithms for Packing d-dimensional Cuboids Into Bins
6: Tiling with Squares and Packing Dominos in Polynomial Time
7: Algorithmic upper bounds for graph geodetic number
8: Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE
9: Searching and Sorting with O(n^2) processors in O(1) time
10: On InstaHide, Phase Retrieval, and Sparse Matrix Factorization
11: An Approximation Algorithm for Covering Linear Programs and its Application to Bin-Packing
12: Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
13: Statistical and computational thresholds for the planted $k$-densest sub-hypergraph problem
14: Speeding up decimal multiplication
15: Analysis of the Harmonic Function Used in Bin-Packing
16: An Estimator for Matching Size in Low Arboricity Graphs with Two Applications
17: Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
18: Selectable Heaps and Optimal Lazy Search Trees
19: InstaHide’s Sample Complexity When Mixing Two Private Images
20: Efficient Approximate Nearest Neighbor Search for Multiple Weighted $l_{p\leq2}$ Distance Functions
21: Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
22: Algorithms and Experiments Comparing Two Hierarchical Drawing Frameworks
23: Min-Sum Clustering (with Outliers)
24: Towards the sampling Lov'asz Local Lemma
25: Optimal Mean Estimation without a Variance
26: Contract Scheduling With Predictions
27: The Geometry of Distributed Representations for Better Alignment, Attenuated Bias, and Improved Interpretability
28: Solving the r-pseudoforest Deletion Problem in Time Independent of r
29: An $O(\log^{3/2}n)$ Parallel Time Population Protocol for Majority with $O(\log n)$ States
30: Left Lyndon tree construction
31: Quantum algorithms for matrix scaling and matrix balancing
32: Grammar Compression By Induced Suffix Sorting
33: Disjoint Stable Matchings in Linear Time
34: Outcome Indistinguishability
35: Faster Projective Clustering Approximation of Big Data
36: Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
37: Tight Hardness Results for Training Depth-2 ReLU Networks
38: Minmax Regret 1-Sink Location Problems on Dynamic Flow Path Networks with Parametric Weights
39: Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs
40: Group-level Fairness Maximization in Online Bipartite Matching
41: Feedback Effects in Repeat-Use Criminal Risk Assessments
42: Windowed Prophet Inequalities