StringologyTimes

Data Structures and Algorithms: 2021/6/01-07

1: Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
2: Sequenceable Event Recorders
3: Optimal Spectral Recovery of a Planted Vector in a Subspace
4: On maximizing a monotone $k$-submodular function under a knapsack constraint
5: A Quasipolynomial $(2+\varepsilon)$-Approximation for Planar Sparsest Cut
6: Optimal Algorithms for Multiwinner Elections and the Chamberlin-Courant Rule
7: Multidimensional Included and Excluded Sums
8: Construction of simplicial complexes with prescribed degree-size sequences
9: Multimodal Transportation with Ridesharing of Personal Vehicles
10: Analysis of classifiers robust to noisy labels
11: $L_0$ Isotonic Regression With Secondary Objectives
12: Junta Distance Approximation with Sub-Exponential Queries
13: Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
14: Boosting the Search Performance of B+-tree for Non-volatile Memory with Sentinels
15: Fault-Tolerant Labeling and Compact Routing Schemes
16: Instance-optimal Mean Estimation Under Differential Privacy
17: Differentially Private Densest Subgraph
18: Optimal Stopping with Behaviorally Biased Agents: The Role of Loss Aversion and Changing Reference Points
19: A (2+\epsilon)-Approximation Algorithm for Maximum Independent Set of Rectangles
20: Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition
21: Public Goods Games in Directed Networks
22: Enabling Efficiency-Precision Trade-offs for Label Trees in Extreme Classification
23: The Generalized Mean Densest Subgraph Problem
24: Ultra-Sparse Near-Additive Emulators
25: Using Predicted Weights for Ad Delivery
26: Efficient Deterministic Leader Election for Programmable Matter
27: MNL-Bandit with Knapsacks: a near-optimal algorithm
28: On the approximation ratio of LZ-End to LZ77
29: Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
30: Transaction Fee Mechanism Design
31: Deterministic Weighted Expander Decomposition in Almost-linear Time
32: Position Heaps for Cartesian-tree Matching on Strings and Tries
33: Internal Shortest Absent Word Queries in Constant Time and Linear Space
34: Component Stability in Low-Space Massively Parallel Computation
35: Low-Congestion Shortcuts in Constant Diameter Graphs
36: Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
37: Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
38: Oblivious Stacking and MAX $k$-CUT for Circle Graphs
39: Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
40: Approximation Algorithms for Min-Distance Problems in DAGs
41: The Algorithmic Phase Transition of Random $k$-SAT for Low Degree Polynomials
42: Optimal Pricing Schemes for an Impatient Buyer
43: Fuzzy Clustering with Similarity Queries
44: A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
45: Parallel and External-Memory Construction of Minimal Perfect Hash Functions with PTHash
46: Spectral Hypergraph Sparsifiers of Nearly Linear Size
47: On Classifying Continuous Constraint Satisfaction Problems
48: Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
49: Algorithms from Invariants: Smoothed Analysis of Orbit Recovery over $SO(3)$
50: Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
51: Dissipative search of an unstructured database
52: Kernel approximation on algebraic varieties
53: Faster and Generalized Temporal Triangle Counting, via Degeneracy Ordering
54: Robust Model Selection and Nearly-Proper Learning for GMMs
55: Optimizing Ansatz Design in QAOA for Max-cut
56: Numerical Composition of Differential Privacy
57: A time and space optimal stable population protocol solving exact majority
58: Time-Optimal Sublinear Algorithms for Matching and Vertex Cover
59: APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
60: Approximate Graph Propagation
61: Faster Cut-Equivalent Trees in Simple Graphs
62: Spectral Independence via Stability and Applications to Holant-Type Problems
63: Network Inference and Influence Maximization from Samples
64: An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
65: Mechanism Design for Facility Location Problems: A Survey
66: SILVAN: Estimating Betweenness Centralities with Progressive Sampling and Non-uniform Rademacher Bounds
67: Local Algorithms for Estimating Effective Resistance
68: An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
69: The Limits of Local Search for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
70: countBF: A General-purpose High Accuracy and Space Efficient Counting Bloom Filter
71: RobustBF: A High Accuracy and Memory Efficient 2D Bloom Filter