Search for: All records

We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most $$c$$ for some $$c = (\log n)^{o(1)}$$. Previously, the best update time was $$\widetilde O(\sqrt{n})$$ for any $c > 2$ and $$c = O(\log n)$$. 

The multicommodity flow problem is a classic problem in network flow and combinatorial optimization, with applications in transportation, communication, logistics, and supply chain management, etc. Existing algorithms often focus on low-accuracy approximate solutions, while high-accuracy algorithms typically rely on general linear program solvers. In this paper, we present efficient high-accuracy algorithms for a broad family of multicommodity flow problems on undirected graphs, demonstrating improved running times compared to general linear program solvers. Our main result shows that we can solve the 𝓁_{q, p}-norm multicommodity flow problem to a (1 + ε) approximation in time O_{q, p}(m^{1+o(1)} k² log(1/ε)), where k is the number of commodities, and O_{q, p}(⋅) hides constants depending only on q or p. As q and p approach to 1 and ∞ respectively, 𝓁_{q, p}-norm flow tends to maximum concurrent flow. We introduce the first iterative refinement framework for 𝓁_{q, p}-norm minimization problems, which reduces the problem to solving a series of decomposable residual problems. In the case of k-commodity flow, each residual problem can be decomposed into k single commodity convex flow problems, each of which can be solved in almost-linear time. As many classical variants of multicommodity flows were shown to be complete for linear programs in the high-accuracy regime [Ding-Kyng-Zhang, ICALP'22], our result provides new directions for studying more efficient high-accuracy multicommodity flow algorithms. 

The group isomorphism problem determines whether two groups, given by their Cayley tables, are isomorphic. For groups with order $$n$$, an algorithm with $$n^{(\log n + O(1))}$$ running time, attributed to Tarjan, was proposed in the 1970s (Miller, STOC 1978). Despite the extensive study over the past decades, the current best group isomorphism algorithm has an $$n^{(1 / 4 + o(1))\log n}$$ running time (Rosenbaum 2013). The isomorphism testing for $$p$$-groups of (nilpotent) class 2 and exponent $$p$$ has been identified as a major barrier to obtaining an $$n^{o(\log n)}$$ time algorithm for the group isomorphism problem. Although the $$p$$-groups of class 2 and exponent $$p$$ have much simpler algebraic structures than general groups, the best-known isomorphism testing algorithm for this group class also has an $$n^{O(\log n)}$$ running time. In this paper, we present an isomorphism testing algorithm for $$p$$-groups of class 2 and exponent $$p$$ with running time $$n^{O((\log n)^{5/6})}$$ for any prime $p > 2$. Our result is based on a novel reduction to the skew-symmetric matrix tuple isometry problem (Ivanyos and Qiao, SIAM J. Computing, 2019). To obtain the reduction, we develop several tools for matrix space analysis, including a matrix space individualization-refinement method and a characterization of the low rank matrix spaces.