The field of complexity theory and algorithms is rapidly advancing, with significant developments in various areas. One of the key directions is the study of oblivious complexity classes, which has led to new lower bounds and hierarchies. Additionally, there have been breakthroughs in dynamic algorithms, including new results on dynamic matching, maximum flow, and minimum cut. The study of distributed algorithms has also seen significant progress, with new lower bounds and algorithms for problems such as maximal matching and vertex coloring. Furthermore, there have been advances in the area of approximation algorithms, including new results on bipartite matching and min-cost flow. Noteworthy papers include: Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies, which proves a hierarchy theorem for O_2TIME and makes partial progress towards resolving an open question posed by Goldreich and Meir. Another notable paper is Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs, which gives a combinatorial algorithm for computing exact maximum flows in directed graphs.
Advances in Complexity Theory and Algorithms
Sources
Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
(Almost) Perfect Discrete Iterative Load Balancing
A Post-Quantum Lower Bound for the Distributed Lov\'asz Local Lemma
The Strongly Stable Roommates Problem and Linear Programming
All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
On the Universality of Round Elimination Fixed Points
Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
Efficiently Batching Unambiguous Interactive Proofs
On the Randomized Locality of Matching Problems in Regular Graphs
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
New Hardness Results for the LOCAL Model via a Simple Self-Reduction
On Hardness and Approximation of Broadcasting in Sparse Graphs
Optimal Rounding for Two-Stage Bipartite Matching
Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Parallel $(1+\epsilon)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work