Product Information
Description
An annual survey of the cs.DS arXiv category, covering research published from September 2025 – August 2026. Built on a close-reading set of 132 papers and organised into 37 chapters, it maps the year by the field's research sub-directions.
Book framework (share of the year's output):
- Dynamic Graph Algorithms and Efficient Sampling (20.7%) — Focuses on fast, space-efficient, and parallel algorithms for dynamic graph maintenance, consistent submodular maximization, and low-variance discrete sampling.
- Temporal Graphs and Structural Graph Complexity (13.4%) — Investigates algorithmic complexity and structural properties of temporal graphs, bipartite graphs, and sparse graph classes, including kernelization and spectral recovery.
- Parameterized Complexity and Computational Hardness (10.1%) — Analyzes the parameterized complexity and computational hardness of problems such as vertex coloring, matching, and path finding, often establishing ETH-tight bounds.
- Quantum Algorithms and Learning-Augmented Models (10.0%) — Explores quantum counting, learning-augmented algorithms, and statistical testing methods for distributions, including robust geometric medians and entropy equivalence.
- Sublinear and Near-Linear Time Algorithms (8.3%) — Develops algorithms with sublinear or near-linear time and space complexity for tasks like matrix approximation, stream processing, and linear regression under noise.
- Approximation Algorithms and Submodular Optimization (8.2%) — Designs improved approximation algorithms for NP-hard problems, with a focus on submodular maximization under noise, stable matchings, and sparse subgraph problems.
- Online Algorithms and Competitive Analysis (7.2%) — Studies online resource allocation, matching, and scheduling problems, analyzing competitive ratios and hardness for online convex optimization and discrepancy minimization.
- Lower Bounds and Streaming Complexity (6.2%) — Establishes tight lower bounds for computational problems in streaming, privacy-preserving estimation, and property testing, often using information-theoretic arguments.
- Improved Approximation and Exact Algorithms (5.6%) — Presents algorithms with improved approximation factors or exact solutions for specific problems like integer linear programming, pattern counting, and log-concave sampling.
- Optimal Transport and Near-Optimal Sketching (5.5%) — Focuses on near-optimal bounds and algorithms for optimal transport, sketching matrix norms, and sequential testing with heterogeneous models.
- Tree Algorithms and Network Spanning Structures (4.9%) — Examines algorithms for spanning trees, search trees, and network optimization, including directed spanning tree optimization and B-tree fragmentation analysis.
Each sub-direction is covered across three chapters — how it framed its questions, the strength of its key findings, and its open debates and frontiers — so the reader gets a traceable picture of what this part of the field actually produced over the year.
