StringologyTimes

Data Structures and Algorithms: 2023/5/22-28

1: Marriage and Roommate
2: An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs
3: Approximating a RUM from Distributions on k-Slates
4: Time Fairness in Online Knapsack Problems
5: Error-Tolerant Exact Query Learning of Finite Set Partitions with Same-Cluster Oracle
6: Differentially Private Medians and Interior Points for Non-Pathological Data
7: The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
8: Single-Pass Pivot Algorithm for Correlation Clustering. Keep it simple!
9: Parameterized Complexity Classification for Interval Constraints
10: Fast Maximal Quasi-clique Enumeration: A Pruning and Branching Co-Design Approach
11: A Distributed Conductance Tester Without Global Information Collection
12: Distributed CONGEST Algorithms against Mobile Adversaries
13: Statistical Indistinguishability of Learning Algorithms
14: Engineering Rank/Select Data Structures for Large-Alphabet Strings
15: Deterministic Algorithmic Approaches to Solve Generalised Wordle
16: Automated Tail Bound Analysis for Probabilistic Recurrence Relations
17: Fairness in Streaming Submodular Maximization over a Matroid Constraint
18: Polynomial-Time Pseudodeterministic Construction of Primes
19: Approximating Multiobjective Optimization Problems: How exact can you be?
20: Using Scalarizations for the Approximation of Multiobjective Optimization Problems: Towards a General Theory
21: Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time
22: Algorithms for the Bin Packing Problem with Scenarios
23: Adaptive Data Analysis in a Balanced Adversarial Model
24: Trading Prophets
25: Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
26: Maximizing Neutrality in News Ordering
27: Smoothed Complexity of SWAP in Local Graph Partitioning
28: Online and Streaming Algorithms for Constrained $k$-Submodular Maximization
29: Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements
30: Efficient Approximation Algorithms for Spanning Centrality
31: Polylogarithmic Approximation for Robust s-t Path
32: Sliding Window Sum Algorithms for Deep Neural Networks
33: Efficient Computation of Quantiles over Joins
34: CARAMEL: A Succinct Read-Only Lookup Table via Compressed Static Functions
35: Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs
36: Can You Solve Closest String Faster than Exhaustive Search?
37: Universal Weak Coreset
38: Feature Adaptation for Sparse Linear Regression
39: Differentially Private Low-dimensional Synthetic Data from High-dimensional Datasets
40: Online Dynamic Acknowledgement with Learned Predictions
41: Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
42: Clip-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments
43: Irreducibility of Recombination Markov Chains in the Triangular Lattice
44: DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication
45: Finding Diameter-Reducing Shortcuts in Trees
46: Overlapping and Robust Edge-Colored Clustering in Hypergraphs
47: Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient
48: One stone, two birds: A lightweight multidimensional learned index with cardinality support