StringologyTimes

Data Structures and Algorithms: 2021/12/15-21

1: A faster algorithm for Cops and Robbers
2: Reconfiguring Shortest Paths in Graphs
3: Simulating Random Walks in Random Streams
4: Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time
5: Tight query complexity bounds for learning graph partitions
6: Combating Collusion Rings is Hard but Possible
7: Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
8: Maximum likelihood estimation for randomized shortest paths with trajectory data
9: Minimizing Reachability Times on Temporal Graphs via Shifting Labels
10: Variational Quantum Algorithms for Semidefinite Programming
11: Deciding twin-width at most 4 is NP-complete
12: Hierarchical Clustering: $O(1)$-Approximation for Well-Clustered Graphs
13: Non-Gaussian Component Analysis via Lattice Basis Reduction
14: Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound
15: Disconnected Matchings
16: Min-cost-flow preserving bijection between subgraphs and orientations
17: An Exact Algorithm for the Linear Tape Scheduling Problem
18: Towards a Complexity Classification of LCL Problems in Massively Parallel Computation
19: Beyond Single-Deletion Correcting Codes: Substitutions and Transpositions
20: Scalable Bicriteria Algorithms for Non-Monotone Submodular Cover
21: Weisfeiler and Leman go Machine Learning: The Story so far
22: Pure Differential Privacy from Secure Intermediaries
23: Parameterized Approximation Algorithms for $k$-Center Clustering and Variants
24: Parameterized Algorithms for Kidney Exchange
25: String Sampling with Bidirectional String Anchors
26: Improving Ranking Quality and Fairness in Swiss-System Chess Tournaments
27: The Cascading Metric Tree
28: Accelerating Clique Counting in Sparse Real-World Graphs via Communication-Reducing Optimizations
29: Minimizing Congestion for Balanced Dominators
30: Lower Bounds for Sparse Oblivious Subspace Embeddings
31: Counting Simplices in Hypergraph Streams
32: Efficient reductions and algorithms for variants of Subset Sum
33: Empirically Improved Tokuda Gap Sequence in Shellsort
34: Optimal Gap Sequences in Shellsort for $n\leq16$ Elements