StringologyTimes

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

1: Beating $(1-1/e)$-Approximation for Weighted Stochastic Matching
2: GPU-friendly, Parallel, and (Almost-)In-Place Construction of Left-Balanced k-d Trees
3: Composable Coresets for Constrained Determinant Maximization and Beyond
4: Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs
5: A Near-Linear Kernel for Two-Parsimony Distance
6: On the zeroes of hypergraph independence polynomials
7: Simplified Prophet Inequalities for Combinatorial Auctions
8: Alternative polynomial-time algorithm for Bipartite Matching
9: Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation
10: Benchmarking Hashing Algorithms for Load Balancing in a Distributed Database Environment
11: Balancing Utility and Fairness in Submodular Maximization (Technical Report)
12: On Correlation Detection and Alignment Recovery of Gaussian Databases
13: Set Selection under Explorable Stochastic Uncertainty via Covering Techniques
14: New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
15: Deep Distance Sensitivity Oracles
16: Cluster Assignment in Multi-Agent Systems : Sparsity Bounds and Fault Tolerance
17: A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
18: Computing a many-to-many matching with demands and capacities between two sets using the Hungarian algorithm
19: Pairing optimization via statistics: Algebraic structure in pairing problems and its application to performance enhancement
20: Round and Bipartize for Vertex Cover Approximation
21: Efficient Branch-and-Bound Algorithms for Finding Triangle-Constrained 2-Clubs
22: Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
23: Distributed Reconfiguration of Spanning Trees
24: SQUID: Faster Analytics via Sampled Quantile Estimation
25: Complexity of Simon’s problem in classical sense
26: Matching Augmentation via Simultaneous Contractions
27: Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
28: Truthful Matching with Online Items and Offline Agents
29: Competitive Kill-and-Restart and Preemptive Strategies for Non-Clairvoyant Scheduling
30: Variable Parameter Analysis for Scheduling One Machine
31: Privacy-preserving Deep Learning based Record Linkage
32: Connected k-Center and k-Diameter Clustering
33: Certification with an NP Oracle
34: Online Matching with Set and Concave Delays
35: Online Learning and Bandits with Queried Hints
36: A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
37: A Framework for Approximation Schemes on Disk Graphs
38: Extension of Simple Algorithms to the Matroid Secretary Problem
39: Online Nash Welfare Maximization Without Predictions
40: Balancing graph Voronoi diagrams with one more vertex
41: 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
42: On Vertex Bisection Width of Random $d$-Regular Graphs
43: Approximate Trace Reconstruction from a Single Trace
44: Stochastic Solutions for Dense Subgraph Discovery in Multilayer Networks
45: Partially Disjoint k Shortest Paths
46: Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in $k^2$ and Linear in $n$
47: Towards derandomising Markov chain Monte Carlo
48: Optimal Deterministic Massively Parallel Connectivity on Forests
49: Towards an Optimal Contention Resolution Scheme for Matchings
50: A Simple Combinatorial Algorithm for Robust Matroid Center