StringologyTimes

Data Structures and Algorithms: 2022/11/15-21

1: Efficient algorithms for certifying lower bounds on the discrepancy of random matrices
2: Fast Distributed Brooks’ Theorem
3: Augmented Thresholds for MONI
4: Massively Parallel Algorithms for $b$-Matching
5: On Sparsification of Stochastic Packing Problems
6: Genome-on-Diet: Taming Large-Scale Genomic Analyses via Sparsified Genomics
7: The RED-BLUE SEPARATION problem on graphs
8: Approximating Flexible Graph Connectivity via R"acke Tree based Rounding
9: SDPs and Robust Satisfiability of Promise CSP
10: Optimizing Polymatroid Functions
11: Bandit Algorithms for Prophet Inequality and Pandora’s Box
12: A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
13: Beyond Worst-Case Budget-Feasible Mechanism Design
14: Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
15: Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
16: On the complexity of implementing Trotter steps
17: Learning-Augmented B-Trees
18: Near-Optimal Distributed Computation of Small Vertex Cuts
19: (Re)packing Equal Disks into Rectangle
20: Incremental Approximate Maximum Flow in $m^{1/2+o(1)}$ update time
21: A (simple) classical algorithm for estimating Betti numbers
22: Minimum Path Cover in Parameterized Linear Time
23: Rounding via Low Dimensional Embeddings
24: Extensions of the $(p,q)$-Flexible-Graph-Connectivity model
25: Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues
26: Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
27: Listing 4-Cycles
28: The communication cost of security and privacy in federated frequency estimation
29: Identifying Correlation in Stream of Samples
30: Improved Approximations for Unrelated Machine Scheduling
31: Prophet-Inequalities over Time
32: Efficient Determinant Maximization for All Matroids
33: PIM-tree: A Skew-resistant Index for Processing-in-Memory
34: A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems
35: Differential Privacy from Locally Adjustable Graph Algorithms: $k$-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
36: Optimal resizable arrays
37: Lemmas of Differential Privacy
38: Toeplitz Low-Rank Approximation with Sublinear Query Complexity
39: Estimating the Effective Support Size in Constant Query Complexity
40: Expander Decomposition in Dynamic Streams