StringologyTimes

Data Structures and Algorithms: 2024/10/22-28

1: Streaming and Communication Complexity of Load-Balancing via Matching Contractors
2: 3SUM in Preprocessed Universes: Faster and Simpler
3: The Parameterized Complexity Landscape of the Unsplittable Flow Problem
4: EFX Allocations and Orientations on Bipartite Multi-graphs: A Complete Picture
5: Deep Learning and Machine Learning – Python Data Structures and Mathematics Fundamental: From Theory to Practice
6: Covariance estimation using Markov chain Monte Carlo
7: Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
8: Parallel Cluster-BFS and Applications to Shortest Paths
9: Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error
10: Computing Optimal Regularizers for Online Linear Optimization
11: A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
12: Sketching, Moment Estimation, and the L'evy-Khintchine Representation Theorem
13: Validating a PTAS for Triangle-Free 2-Matching via a Simple Decomposition Theorem
14: Collision-free Exploration by Mobile Agents Using Pebbles
15: Fixed-Parameter Tractability of Hedge Cut
16: Tight Bounds for Online Balanced Partitioning in the Generalized Learning Model
17: On the formalization of the notion of a concurrent algorithm
18: Privacy-Computation trade-offs in Private Repetition and Metaselection
19: Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization
20: Lower Bounds for Convexity Testing
21: Quantum linear system algorithm with optimal queries to initial state preparation
22: Locally seeded embeddings, and Ramsey numbers of bipartite graphs with sublinear bandwidth
23: Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs
24: Stronger adversaries grow cheaper forests: online node-weighted Steiner problems
25: Counting Locally Optimal Tours in the TSP
26: Recognizing Sumsets is NP-Complete
27: Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
28: Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection using Nearly-Linear Independence-Oracle Queries
29: Packing Short Cycles
30: Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
31: Testing Support Size More Efficiently Than Learning Histograms
32: How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
33: Learning $k$-body Hamiltonians via compressed sensing
34: Matching Composition and Efficient Weight Reduction in Dynamic Matching
35: Min-CSPs on Complete Instances
36: Tera-Scale Multilevel Graph Partitioning
37: Fairness and Efficiency in Online Class Matching
38: Overcoming Non-Submodularity: Constant Approximation for Network Immunization
39: Paths and Intersections: Characterization of Quasi-metrics in Directed Okamura-Seymour Instances
40: Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
41: Dynamic O(arboricity) coloring in polylogarithmic worst-case time
42: Improved Hardness-of-Approximation for Token Swapping
43: Low-degree spanning trees of $2$-edge-connected graphs in linear time
44: Solving Polynomial Equations Over Finite Fields
45: On the I/O Complexity of the CYK Algorithm and of a Family of Related DP Algorithms
46: Improved Online Reachability Preservers
47: On Sparsest Cut and Conductance in Directed Polymatroidal Networks
48: A New Method for Inserting Train Paths into a Timetable
49: Parameterized Saga of First-Fit and Last-Fit Coloring
50: New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
51: Fully-Distributed Byzantine Agreement in Sparse Networks
52: Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
53: Popping Bubbles in Pangenome Graphs
54: A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
55: Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic