StringologyTimes

Data Structures and Algorithms: 2025/8/01-07

1: Nyldon Factorization of Thue-Morse Words and Fibonacci Words
2: Amplitude amplification and estimation require inverses
3: Are controlled unitaries helpful?
4: Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
5: From Dynamic Programs to Greedy Algorithms
6: Efficient Direct-Access Ranked Retrieval
7: PageRank Centrality in Directed Graphs with Bounded In-Degree
8: Deterministic Fault-Tolerant Local Load Balancing and its Applications against Adaptive Adversaries
9: Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
10: Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation
11: Faster Distributed $\Delta$-Coloring via a Reduction to MIS
12: Fast Gaussian process inference by exact Mat'ern kernel decomposition
13: An Improved Bound for the Beck-Fiala Conjecture
14: Robust Detection of Planted Subgraphs in Semi-Random Models
15: Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
16: Testing Quasiperiodicity
17: A Threshold Phenomenon for the Shortest Lattice Vector Problem in the Infinity Norm
18: Facility Location and $k$-Median with Fair Outliers
19: Instance-Optimal Uniformity Testing and Tracking
20: Finding Colorings in One-Sided Expanders
21: Coloring 3-Colorable Graphs with Low Threshold Rank
22: When is String Reconstruction using de Bruijn Graphs Hard?
23: A 60-Addition, Rank-23 Scheme for Exact 3x3 Matrix Multiplication
24: Counting Distinct Square Substrings in Sublinear Time
25: Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml'os Bounds Beyond Banaszczyk
26: Exactly simulating stochastic chemical reaction networks in sub-constant time per reaction
27: Exact Matching in Matrix Multiplication Time
28: Polynomial-time sampling despite disorder chaos
29: Approximation Algorithms for Scheduling Crowdsourcing Tasks in Mobile Social Networks
30: Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
31: A Refutation of Elmasry’s $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
32: Minimum-Weight Parity Factor Decoder for Quantum Error Correction
33: Necessity of Block Designs for Optimal Locally Private Distribution Estimation
34: Text Indexing and Pattern Matching with Ephemeral Edits
35: Space-Efficient Hierholzer: Eulerian Cycles in O(m) Time and O(n) Space
36: Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size
37: Online Sparsification of Bipartite-Like Clusters in Graphs
38: Parameterized complexity of isometric path partition: treewidth and diameter
39: Algorithmic Delegated Choice: An Annotated Reading List