StringologyTimes

Data Structures and Algorithms: 2020/10/15-21

1: Fast Generation of Unlabelled Free Trees using Weight Sequences
2: Online Learning with Vector Costs and Bandits with Knapsacks
3: Fairness in Streaming Submodular Maximization: Algorithms and Hardness
4: An Approximate Dynamic Programming Approach to The Incremental Knapsack Problem
5: Large Very Dense Subgraphs in a Stream of Edges
6: Adaptive and Universal Algorithms for Variational Inequalities with Optimal Convergence
7: Improved Approximation Algorithms for Stochastic-Matching Problems
8: Sorting Short Keys in Circuits of Size o(n log n)
9: Scheduling Opportunistic Links in Two-Tiered Reconfigurable Datacenters
10: Efficient constructions of the Prefer-same and Prefer-opposite de Bruijn sequences
11: An Algorithm for Learning Smaller Representations of Models With Scarce Data
12: Ranked enumeration of MSO logic on words
13: Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
14: A symmetric attractor-decomposition lifting algorithm for parity games
15: Restless reachability problems in temporal graphs
16: An Approximation Algorithm for Optimal Subarchitecture Extraction
17: Learnable Graph-regularization for Matrix Decomposition
18: Improving Schroeppel and Shamir’s Algorithm for Subset Sum via Orthogonal Vectors
19: Universal guarantees for decision tree induction via a higher-order splitting criterion
20: Fast Spatial Autocorrelation
21: On the Hardness of Average-case k-SUM
22: Lazy Search Trees
23: Solving Shisen-Sho boards
24: On Near-Linear-Time Algorithms for Dense Subset Sum
25: Shortest Paths Among Obstacles in the Plane Revisited
26: Diverse Data Selection under Fairness Constraints
27: The Graphs of Stably Matchable Pairs
28: Leader Election And Local Identifiers For 3D Programmable Matter
29: EPTAS for $k$-means Clustering of Affine Subspaces
30: Hutch++: Optimal Stochastic Trace Estimation
31: Constrained-Order Prophet Inequalities
32: Evaluating the Cost of Atomic Operations on Modern Architectures
33: SlimSell: A Vectorizable Graph Representation for Breadth-First Search
34: On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians
35: New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
36: Scalable Shared-Memory Hypergraph Partitioning
37: The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
38: A Faster Parameterized Algorithm for Temporal Matching
39: A practical algorithm to calculate Cap Discrepancy
40: A Note on the Approximability of Deepest-Descent Circuit Steps
41: Multi-Dimensional Randomized Response