Misc.
[Irmak, Mihaylov, Suel, 05] Improved single-round protocols for remote file synchronization.
[Clifford, Kociumaka, Porat, SODA'19] The streaming k-mismatch problem.
Global minimum cut
Minimum Cuts in Near-Linear Time. [read] randomized, undirected, weighted, $\tilde{O}(m)$, hide a factor $O(m\log^3n)$.
Deterministic Edge Connectivity in Near-Linear Time. deterministic, undirected, unweighted, $\tilde{O}(m)$, hide a factor $O(\log^{12}n)$ which is large.
Local Flow Partitioning for Faster Edge Connectivity. deterministic, undirected. unweighted, improves the factor to $O(m\log^2n\log\log^2n)$. Add a factor $\alpha^4$ for $\alpha$-balanced directed graph (every cut is $\alpha$ balanced regarding in-out edge).
Deterministic Mincut in Almost-Linear Time. deterministic, undirected, weighted in $O(m^{1+o(1)})$ time. Previous work Deterministic Min-cut in Poly-logarithmic Max-flows calls $polylog(m)^{1/\epsilon}$ times of maxflow and use $O(m^{1+\epsilon})$ time.
Minimum Cuts in Directed Graphs via Partial Sparsification. Randomized, directed, weighted. $\tilde{O}(nm^{2/3}+n^{2})$ time algorithm.
Vertex Connectivity
Computing Vertex Connectivity: New Bounds from Old Techniques. randomized $\tilde{O}(mn)$ for both directed and undirected.
Using Expander Graphs to Find Vertex Connectivity. derterministic for both, time $O(mn+mk^{5/2}+mn^{3/4}k)$.
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms. [read] Randomized roughly $\tilde{O}(k^2m)$ for both. $\tilde{O}(m)$ for $k=poly(\log n)$, which is the best one for small $k$ (roughly under $n^{0.456}$).
Vertex Connectivity in Poly-logarithmic Max-Flows. [read] Randomized, $\tilde{O}(m^{\alpha})$ time using a $\tilde{O}(m^{\alpha})$ max flow algorithm for $\alpha\ge 1$.
Max-Flow
Unit Capacity Maxflow in Almost $O(m^{4/3})$ Time. derterministic, directed, $O(m^{4/3+o(1)}U^{1/3})$ time where $U$ is the maximum capacity.
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs. randomized, $\tilde{O}(m+n^{1.5})$.