{"ID":2861108,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.03427","arxiv_id":"2510.03427","title":"A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow","abstract":"In this paper, we discuss the maximum flow problem in the two-party communication model, where two parties, each holding a subset of edges on a common vertex set, aim to compute the maximum flow of the union graph with minimal communication. We show that this can be solved with $\\tilde{O}(n^{1.5})$ bits of communication, improving upon the trivial $\\tilde{O}(n^2)$ bound. To achieve this, we derive two additional, more general results: 1. We present a randomized algorithm for linear programs with two-sided constraints that requires $\\tilde{O}(n^{1.5}k)$ bits of communication when each constraint has at most $k$ non-zeros. This result improves upon the prior work by [Ghadiri, Lee, Padmanabhan, Swartworth, Woodruff, Ye, STOC'24], which achieves a complexity of $\\tilde{O}(n^2)$ bits for LPs with one-sided constraints. Upon more precise analysis, their algorithm can reach a bit complexity of $\\tilde{O}(n^{1.5} + nk)$ for one-sided constraint LPs. Nevertheless, for sparse matrices, our approach matches this complexity while extending the scope to two-sided constraints. 2. Leveraging this result, we demonstrate that the minimum cost flow problem, as a special case of solving linear programs with two-sided constraints and as a general case of maximum flow problem, can also be solved with a communication complexity of $\\tilde{O}(n^{1.5})$ bits. These results are achieved by adapting an interior-point method (IPM)-based algorithm for solving LPs with two-sided constraints in the sequential setting by [van den Brand, Lee, Liu, Saranurak, Sidford, Song, Wang, STOC'21] to the two-party communication model. This adaptation utilizes techniques developed by [Ghadiri, Lee, Padmanabhan, Swartworth, Woodruff, Ye, STOC'24] for distributed convex optimization.","short_abstract":"In this paper, we discuss the maximum flow problem in the two-party communication model, where two parties, each holding a subset of edges on a common vertex set, aim to compute the maximum flow of the union graph with minimal communication. We show that this can be solved with $\\tilde{O}(n^{1.5})$ bits of communicatio...","url_abs":"https://arxiv.org/abs/2510.03427","url_pdf":"https://arxiv.org/pdf/2510.03427v1","authors":"[\"Hossein Gholizadeh\",\"Yonggang Jiang\"]","published":"2025-10-03T18:43:12Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\"]","methods":"[]","has_code":false}