StringologyTimes

Data Structures and Algorithms: 2023/1/22-28

1: Statistically Optimal Robust Mean and Covariance Estimation for Anisotropic Gaussians
2: A graph isomorphism invariant based on neighborhood aggregation
3: Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model
4: Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
5: A New Approximation Algorithm for Minimum-Weight $(1,m)$–Connected Dominating Set
6: Improved Hardness of Approximation for Geometric Bin Packing
7: Approximating Knapsack and Partition via Dense Subset Sums
8: A New Dynamic Programming Approach for Spanning Trees with Chain Constraints and Beyond
9: Sliding Window String Indexing in Streams
10: A New Approach to Learning Linear Dynamical Systems
11: The Impossibility of Parallelizing Boosting
12: Balanced Allocations with Heterogeneous Bins: The Power of Memory
13: Treewidth is NP-Complete on Cubic Graphs (and related results)
14: Improved Pseudorandom Generators for $\mathsf{AC}^0$ Circuits
15: Distinct Elements in Streams: An Algorithm for the (Text) Book
16: Capacity Analysis of Vector Symbolic Architectures
17: Online variable-weight scheduling with preempting on jobs with linear and exponential penalties
18: Exact and rapid linear clustering of networks with dynamic programming
19: In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
20: Succinct Planar Encoding with Minor Operations
21: Compatibility of convergence algorithms for autonomous mobile robots
22: WL meet VC
23: Deterministic Massively Parallel Symmetry Breaking for Sparse Graphs
24: The Quantum Alternating Operator Ansatz for Satisfiability Problems
25: AdaBoost is not an Optimal Weak to Strong Learner
26: Semi-Supervised Machine Learning: a Homological Approach
27: A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees
28: Algorithms for ranking and unranking the combinatorial set of RNA secondary structures
29: Efficient Enumeration of Markov Equivalent DAGs