StringologyTimes

Data Structures and Algorithms: 2023/2/01-07

1: p-median location interdiction on trees
2: Flipper games for monadically stable graph classes
3: Multicalibration as Boosting for Regression
4: Bounds for c-Ideal Hashing
5: General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation
6: Zero-Memory Graph Exploration with Unknown Inports
7: On the Within-Group Fairness of Screening Classifiers
8: Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees
9: Exploring Wedges of an Oriented Grid by an Automaton with Pebbles
10: Adding an Edge in a $P_4$-sparse Graph
11: Sublinear Approximation Schemes for Scheduling Precedence Graphs of Bounded Depth
12: Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining
13: Approximating Red-Blue Set Cover and Minimum Monotone Satisfying Assignment
14: A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee
15: Flip-width: Cops and Robber on dense graphs
16: Faster maximal clique enumeration in large real-world link streams
17: Improved Exact and Heuristic Algorithms for Maximum Weight Clique
18: The Investment Management Game: Extending the Scope of the Notion of Core
19: Parameterized Algorithms for Colored Clustering
20: Adding a Tail in Classes of Perfect Graphs
21: Order-Preserving Squares in Strings
22: A Universal Technique for Machine-Certified Proofs of Linearizable Algorithms
23: Constant RMR Recoverable Mutex under System-wide Crashes
24: Rethinking Warm-Starts with Predictions: Learning Predictions Close to Sets of Optimal Solutions for Faster $\text{L}$-/$\text{L}^\natural$-Convex Function Minimization
25: Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary
26: Explicit two-sided unique-neighbor expanders
27: Optimal Heaviest Induced Ancestors
28: Complexity of Solo Chess with Unlimited Moves
29: Group Fairness in Non-monotone Submodular Maximization
30: Chaining of Maximal Exact Matches in Graphs
31: Online Ad Allocation with Predictions
32: Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra
33: Robust Budget Pacing with a Single Sample
34: Sketch-Flip-Merge: Mergeable Sketches for Private Distinct Counting
35: An Effective and Differentially Private Protocol for Secure Distributed Cardinality Estimation
36: On 2-strong connectivity orientations of mixed graphs and related problems
37: Maximal $k$-Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction
38: KDEformer: Accelerating Transformers via Kernel Density Estimation
39: Stochastic Minimum Vertex Cover in General Graphs: a $3/2$-Approximation
40: Optimal LZ-End Parsing is Hard
41: Models and algorithms for simple disjunctive temporal problems
42: Optimally Interpolating between Ex-Ante Fairness and Welfare
43: Sparsification of Monotone $k$-Submodular Functions of Low Curvature
44: Calibrated Recommendations for Users with Decaying Attention
45: Two Parallel PageRank Algorithms via Improving Forward Push
46: Engineering Shared-Memory Parallel Shuffling to Generate Random Permutations In-Place
47: The Solidarity Cover Problem
48: 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
49: Storing a Trie with Compact and Predictable Space