StringologyTimes

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

1: Exact Algorithms for MaxCut on Split Graphs
2: Finding Diverse Solutions Parameterized by Cliquewidth
3: Submodular Maximization in Exactly $n$ Queries
4: Individual Fairness in Graph Decomposition
5: Counting on General Run-Length Grammars
6: Optimal bounds for $\ell_p$ sensitivity sampling via $\ell_2$ augmentation
7: Turnstile $\ell_p$ leverage score sampling with applications
8: Better coloring of 3-colorable graphs
9: Approaching 100% Confidence in Stream Summary through ReliableSketch
10: Structural and algorithmic results for stable cycles and partitions in the Roommates problem
11: Robust Fair Clustering with Group Membership Uncertainty Sets
12: Sample Complexity of Posted Pricing for a Single Item
13: Faster Diffusion-based Sampling with Randomized Midpoints: Sequential and Parallel
14: Knapsack with Vertex Cover, Set Cover, and Hitting Set
15: Profile Reconstruction from Private Sketches
16: Linear Index for Logarithmic Search-Time for any String under any Internal Node in Suffix Trees
17: Polynomial Bounds of CFLOBDDs against BDDs
18: A Surprisingly Simple Method for Distributed Euclidean-Minimum Spanning Tree / Single Linkage Dendrogram Construction from High Dimensional Embeddings via Distance Decomposition
19: On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
20: Convergence Properties of the Asynchronous Maximum Model
21: Influence Maximization in Hypergraphs by Stratified Sampling for Efficient Generation of Reverse Reachable Sets
22: Random Abstract Cell Complexes
23: On the Computation of 2-Dimensional Recurrence Equations
24: Almost linear time differentially private release of synthetic graphs
25: The complexity of approximate (coarse) correlated equilibrium for incomplete information games
26: Replicability in High Dimensional Statistics
27: Differentially private exact recovery for stochastic block models
28: Reweighted Solutions for Weighted Low Rank Approximation
29: Coresets for Multiple $\ell_p$ Regression
30: Singular Subspace Perturbation Bounds via Rectangular Random Matrix Diffusions
31: GEFL: Extended Filtration Learning for Graph Classification
32: Local Search k-means++ with Foresight
33: Tolerant Algorithms for Learning with Arbitrary Covariate Shift
34: Efficient Leverage Score Sampling for Tensor Train Decomposition
35: Indexing Finite-State Automata Using Forward-Stable Partitions
36: Private Stochastic Convex Optimization with Heavy Tails: Near-Optimality from Simple Reductions
37: A Bi-metric Framework for Fast Similarity Search
38: High-Dimensional Geometric Streaming for Nearly Low Rank Data
39: Quantum Algorithms and Lower Bounds for Finite-Sum Optimization
40: Dynamic Spectral Clustering with Provable Approximation Guarantee
41: Brief Announcement: Distributed Unconstrained Local Search for Multilevel Graph Partitioning
42: A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives
43: Private Online Learning via Lazy Algorithms
44: Finding maximum matchings in RDV graphs efficiently
45: Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
46: Bidding in Uniform Price Auctions for Value Maximizing Buyers
47: A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
48: Continual Counting with Gradual Privacy Expiration
49: Engineering Semi-streaming DFS algorithms
50: Eigenpath traversal by Poisson-distributed phase randomisation
51: L’algorithme: pourquoi et comment le d'efinir pour l’enseigner
52: On the zeros of partition functions with multi-spin interactions
53: The CLRS-Text Algorithmic Reasoning Language Benchmark
54: On the Expressive Power of Spectral Invariant Graph Neural Networks
55: A Lower Bound for Light Spanners in General Graphs
56: Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
57: In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
58: Learning-Augmented Priority Queues
59: A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering
60: Multi-View Stochastic Block Models
61: Perturb-and-Project: Differentially Private Similarities and Marginals
62: Optimized Deletion From an AVL Tree
63: Spectral Toolkit of Algorithms for Graphs: Technical Report (2)