StringologyTimes

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

1: Iterated Straight-Line Programs
2: Efficient Unitary T-designs from Random Sums
3: A Modern Approach to Electoral Delimitation using the Quadtree Data Structure
4: Fixed-sparsity matrix approximation from matrix-vector products
5: Unbalanced Random Matching Markets with Partial Preferences
6: Robust Learning-Augmented Dictionaries
7: On the adversarial robustness of Locality-Sensitive Hashing in Hamming space
8: Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
9: Parameterized Vertex Integrity Revisited
10: A Piecewise Approach for the Analysis of Exact Algorithms
11: Quantum Backtracking in Qrisp Applied to Sudoku Problems
12: Trainability Barriers in Low-Depth QAOA Landscapes
13: Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
14: Correlation Clustering with Vertex Splitting
15: Non-adaptive Bellman-Ford: Yen’s improvement is optimal
16: Transductive Learning Is Compact
17: Collaborative Learning with Different Labeling Functions
18: Composition Orderings for Linear Functions and Matrix Multiplication Orderings
19: Learning-Augmented Skip Lists
20: Alphabet Reduction for Reconfiguration Problems
21: Probability Tools for Sequential Random Projection
22: On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
23: Streaming Algorithms for Connectivity Augmentation
24: Core Stability in Additively Separable Hedonic Games of Low Treewidth
25: Hypergraph Connectivity Augmentation in Strongly Polynomial Time
26: Incremental Topological Ordering and Cycle Detection with Predictions
27: The Competition Complexity of Prophet Inequalities
28: Online Flexible Busy Time Scheduling on Heterogeneous Machines
29: Private PAC Learning May be Harder than Online Learning
30: Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
31: Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search
32: An Elementary Predictor Obtaining $2\sqrt{T}+1$ Distance to Calibration
33: Approximating Partition in Near-Linear Time
34: A Simple Proof that Ricochet Robots is PSPACE-Complete
35: Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
36: Faster algorithms on linear delta-matroids
37: To Store or Not to Store: a graph theoretical approach for Dataset Versioning
38: Buffered Streaming Edge Partitioning
39: Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
40: Collision-Free Robot Scheduling
41: Causal Equal Protection as Algorithmic Fairness
42: The Complexity of Geodesic Spanners using Steiner Points
43: Connectivity Labeling in Faulty Colored Graphs
44: Local certification of forbidden subgraphs
45: Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
46: Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
47: Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth $p=1$
48: Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
49: Distance Recoloring
50: A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
51: Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
52: Nearly Optimal Fault Tolerant Distance Oracle
53: Locally Rainbow Paths
54: Efficient Enumeration of Large Maximal k-Plexes
55: Scalable Pattern Matching in Computation Graphs
56: Deterministic Dynamic Edge-Colouring
57: Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
58: Clustered Planarity Variants for Level Graphs
59: Improved Space Bounds for Subset Sum
60: Testing Calibration in Nearly-Linear Time
61: Online Matching on $3$-Uniform Hypergraphs
62: Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
63: Structured Tree Alignment for Evaluation of (Speech) Constituency Parsing
64: How to Reduce Temporal Cliques to Find Sparse Spanners
65: ExaLogLog: Space-Efficient and Practical Approximate Distinct Counting up to the Exa-Scale
66: Adaptive Massively Parallel Coloring in Sparse Graphs
67: Equilibria, Efficiency, and Inequality in Network Formation for Hiring and Opportunity
68: Multi-Agent Online Graph Exploration on Cycles and Tadpole Graphs