StringologyTimes

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

1: Efficient top-down updates in AVL trees
2: On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse
3: Fair Secretaries with Unfair Predictions
4: Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
5: Optimal Capacity Modification for Stable Matchings with Ties
6: Ranking and Unranking of the Planar Embeddings of a Planar Graph
7: Hardness Results on Characteristics for Elastic-Degenerated Strings
8: Differentiable Extensions with Rounding Guarantees for Combinatorial Optimization over Permutations
9: Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
10: Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
11: Near-Optimal Averaging Samplers and Matrix Samplers
12: Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
13: The Conflict Graph Design: Estimating Causal Effects under Arbitrary Neighborhood Interference
14: Maximization of Approximately Submodular Functions
15: Fault-Equivalent Lowest Common Ancestors
16: Amortized Analysis of Leftist Heaps
17: Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
18: Approximation algorithms for non-sequential star packing problems
19: Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
20: Reliable Learning of Halfspaces under Gaussian Marginals
21: Massively Parallel Maximum Coverage Revisited
22: On the compressiveness of the Burrows-Wheeler transform
23: SpiderDAN: Matching Augmentation in Demand-Aware Networks
24: Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information
25: The Complexity Landscape of Dynamic Distributed Subgraph Finding
26: Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
27: Hash & Adjust: Competitive Demand-Aware Consistent Hashing
28: Distributed Maximum Flow in Planar Graphs
29: Solving convex QPs with structured sparsity under indicator conditions
30: A Bicriterion Concentration Inequality and Prophet Inequalities for $k$-Fold Matroid Unions
31: Towards Scalable and Practical Batch-Dynamic Connectivity
32: Parsing Millions of DNS Records per Second
33: Matroid Secretary via Labeling Schemes
34: Sorted Consecutive Occurrence Queries in Substrings
35: Space-Efficient Online Computation of String Net Occurrences
36: Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It
37: An Affine Equivalence Algorithm for S-boxes based on Matrix Invariants
38: Brief Announcement: Parallel Construction of Bumped Ribbon Retrieval
39: Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
40: Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing
41: Error Analysis of Sum-Product Algorithms under Stochastic Rounding
42: Statistical inference of a ranked community in a directed graph
43: Reconfiguration Using Generalized Token Jumping
44: Local Density and its Distributed Approximation
45: Weighted Envy Freeness With Bounded Subsidies
46: Learning multivariate Gaussians with imperfect advice
47: Testing classical properties from quantum data
48: Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
49: Omnipredicting Single-Index Models with Multi-Index Models
50: (Independent) Roman Domination Parameterized by Distance to Cluster
51: Parameterized Geometric Graph Modification with Disk Scaling
52: On the structure of normalized models of circular-arc graphs – Hsu’s approach revisited
53: Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
54: Procurement Auctions via Approximately Optimal Submodular Optimization
55: Differentially Private Learning Beyond the Classical Dimensionality Regime
56: Comments on “$\mathcal{O}(m\cdot n)$ algorithms for the recognition and isomorphism problems on circular-arc graphs”
57: Distributed Distance Sensitivity Oracles
58: Dynamic Structural Clustering Unleashed: Flexible Similarities, Versatile Updates and for All Parameters
59: Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices