StringologyTimes

Data Structures and Algorithms: 2024/4/15-21

1: Better space-time-robustness trade-offs for set reconciliation
2: A Circus of Circuits: Connections Between Decision Diagrams, Circuits, and Automata
3: Online Multi-level Aggregation with Delays and Stochastic Arrivals
4: Search-Space Reduction Via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion
5: Parameterized Algorithms for Editing to Uniform Cluster Graph
6: Synthetic Census Data Generation via Multidimensional Multiset Sum
7: Node Similarities under Random Projections: Limits and Pathological Cases
8: Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
9: Bit catastrophes for the Burrows-Wheeler Transform
10: How quickly can you pack short paths? Engineering a search-tree algorithm for disjoint s-t paths of bounded length
11: Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
12: Simple $k$-crashing Plan with a Good Approximation Ratio
13: A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
14: The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
15: The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
16: On approximability of the Permanent of PSD matrices
17: Drawing Competitive Districts in Redistricting
18: Online Algorithms with Limited Data Retention
19: Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
20: On Learning Parities with Dependent Noise
21: Sinking an Algorithmic Isthmus: (1 + {\epsilon})-Approximate Min-Sum Subset Convolution
22: Finding $d$-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and $H$-Free Graphs
23: Testing Intersectingness of Uniform Families
24: The EDGE Language: Extended General Einsums for Graph Algorithms
25: Private federated discovery of out-of-vocabulary words for Gboard
26: Hairpin Completion Distance Lower Bound
27: A Fast Maximum Clique Algorithm Based on Network Decomposition for Large Sparse Networks
28: Public Event Scheduling with Busy Agents
29: A Mathematical Formalisation of the {\gamma}-contraction Problem
30: Effective Individual Fairest Community Search over Heterogeneous Information Networks
31: The graph alignment problem: fundamental limits and efficient algorithms
32: Contract Scheduling with Distributional and Multiple Advice
33: An algorithm with a delay of $\mathcal{O}(k\Delta)$ for enumerating connected induced subgraphs of size $k$
34: Exploiting New Properties of String Net Frequency for Efficient Computation
35: Dynamic Parameterized Feedback Problems in Tournaments
36: Fast Broadcast in Highly Connected Networks
37: Low-Depth Spatial Tree Algorithms
38: Mean-field Potts and random-cluster dynamics from high-entropy initializations
39: On multidimensional generalization of binary search
40: Non-Linear Paging
41: Declarative Concurrent Data Structures
42: New Structures and Algorithms for Length-Constrained Expander Decompositions
43: An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
44: Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
45: Predict to Minimize Swap Regret for All Payoff-Bounded Tasks