StringologyTimes

Data Structures and Algorithms: 2024/4/08-14

1: Chromatic number in $1.9999^n$ time? Fast deterministic set partitioning under the asymptotic rank conjecture
2: Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
3: Directed Buy-at-Bulk Spanners
4: Scheduling Multi-Server Jobs is Not Easy
5: Combinatorial Correlation Clustering
6: Efficient Distributed Data Structures for Future Many-core Architectures
7: BFS versus DFS for random targets in ordered trees
8: Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
9: Balanced Partitioning for Optimizing Big Graph Computation: Complexities and Approximation Algorithms
10: Polynomial-time derivation of optimal k-tree topology from Markov networks
11: AiSAQ: All-in-Storage ANNS with Product Quantization for DRAM-free Information Retrieval
12: The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O(\log n)$ Deterministic Rounds on the Congested Clique
13: Fully Dynamic Matching and Ordered Ruzsa-Szemer'edi Graphs
14: The Overlap Gap Property limits limit swapping in QAOA
15: Algorithms for Caching and MTS with reduced number of predictions
16: Simple algorithms to test and learn local Hamiltonians
17: Optimal Stopping with Interdependent Values
18: Characterizations of Sparsifiability for Affine CSPs and Symmetric CSPs
19: Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
20: A universal sequence of tensors for the asymptotic rank conjecture
21: The Central Spanning Tree Problem
22: On Bounds for Greedy Schemes in String Optimization based on Greedy Curvatures
23: A Reexamination of the COnfLUX 2.5D LU Factorization Algorithm
24: Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
25: Language Generation in the Limit
26: Fully Dynamic Correlation Clustering: Breaking 3-Approximation
27: An asymptotically optimal algorithm for generating bin cardinalities
28: Exploring Repetitiveness Measures for Two-Dimensional Strings
29: Computing the $D$-base and $D$-relation in finite closure systems
30: Generalized Straight-Line Programs
31: A Reexamination of the Communication Bandwidth Cost Analysis of A Parallel Recursive Algorithm for Solving Triangular Systems of Linear Equations
32: Probabilistic estimates of the diameters of the Rubik’s Cube groups
33: Near Optimal Alphabet-Soundness Tradeoff PCPs
34: Dynamic Suffix Array in Optimal Compressed Space
35: Parameterized Complexity of Submodular Minimization under Uncertainty
36: Glauber dynamics for the hard-core model on bounded-degree $H$-free graphs
37: An improvement of degree-based hashing (DBH) graph partition method, using a novel metric
38: An efficient uniqueness theorem for overcomplete tensor decomposition
39: Diagram Analysis of Iterative Algorithms
40: Matrix Multiplication Reductions
41: On the Power of Interactive Proofs for Learning
42: Naively Sorting Evolving Data is Optimal and Robust
43: Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
44: Bottom-up Rebalancing Binary Search Trees by Flipping a Coin
45: Asymptotics of relaxed $k$-ary trees
46: Tight Bounds for Sorting Under Partial Information
47: An improved spectral lower bound of treewidth
48: Approximating the volume of a truncated relaxation of the independence polytope
49: Destroying Densest Subgraphs is Hard
50: Improved Approximations for Flexible Network Design