We give an algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities in $m^{1+o(1)}$ time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized $m^{o(1)}$ time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This...

In this paper we provide new randomized algorithms with improved runtimes for solving linear programs two-sided constraints. the special case of minimum cost flow problem on n-vertex m-edge graphs integer polynomially-bounded costs and capacities obtain a method which solves in Õ(m + n1.5) time. This improves upon previous best runtime √n) [Lee-Sidford'14] and, unit-capacity maximum flow, m4/3 o(1) [Liu-Sidford'20, Kathuria'20] sufficiently dense graphs.

In this paper we provide an algorithm which given any m-edge n-vertex directed graph with integer capacities at most U computes a maximum s-t flow for vertices s and t in m 11/8+o(1) 1/4 time high probability. This running improves upon the previous best of Õ(m 10/7 1/7) (Mądry 2016), √n logU) (Lee Sidford 2014), O(mn) (Orlin 2013) when is not too dense or has large capacities.

We give an algorithm for computing exact maximum flows on graphs with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> edges and integer capacities in the range [ xmlns:xlink="http://www.w3.org/1999/xlink">$1,U$</tex> ] xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(m^{\frac{3}{2}-\frac{1}{328}}\log U)$</tex> time. <sup xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> use...

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, s-t shortest path, maximum flow, and minimum-cost flow. To solve these problems, we a deterministic data structure that returns mo(1)-approximate minimum-ratio fully dynamic amortized mo(1) per update. Combining this with interior point method framework of Brand-Liu-Sidford (STOC 2023) gives algorithm deciding update an graph after...

We present an algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities in 1 + o (1) time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This gives...

.We study discrepancy minimization for vectors in \(\mathbb{R}^n\) under various settings. The main result is the analysis of a new simple random process high dimensions through comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors online vector balancing against oblivious adversaries, resolving several questions posed by Bansal et al. [STOC, ACM, New York, 2020, pp. 1139–1152], as well linear time algorithm Komlós conjecture.Keywordsonline...

We make several advances broadly related to the maintenance of electrical flows in weighted graphs undergoing dynamic resistance updates, including:

We give a deterministic $m^{1+o(1)}$ time algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities. As consequence, we obtain the first running improvement for algorithms compute maximum-flow in polynomial capacities since work of Goldberg-Rao [J.ACM '98].Our builds framework Chen-Kyng-Liu-Peng-Gutenberg-Sachdeva [FOCS '22] an optimal flow by computing sequence $m^{1+o(1)}$-approximate undirected...

In this paper we provide a parallel algorithm that given any n-node m-edge directed graph and source vertex s computes all vertices reachable from with Õ(m) work n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">{1/2</sup> xmlns:xlink="http://www.w3.org/1999/xlink">+</sup> xmlns:xlink="http://www.w3.org/1999/xlink">o(1)</sup> } depth high probability in n. This also set of Õ(n) edges which when added to the preserves reachability ensures...

We study discrepancy minimization for vectors in ℝn under various settings. The main result is the analysis of a new simple random process high dimensions through comparison argument. As corollaries, we obtain bounds which are tight up to logarithmic factors online vector balancing against oblivious adversaries, resolving several questions posed by Bansal, Jiang, Singla, and Sinha (STOC 2020), as well linear time algorithm Komlós conjecture.

In this paper we provide new randomized algorithms with improved runtimes for solving linear programs two-sided constraints. the special case of minimum cost flow problem on $n$-vertex $m$-edge graphs integer polynomially-bounded costs and capacities obtain a method which solves in $\tilde{O}(m+n^{1.5})$ time. This improves upon previous best runtime $\tilde{O}(m\sqrt{n})$ (Lee-Sidford 2014) and, unit-capacity maximum flow, $m^{4/3+o(1)}$ (Liu-Sidford 2020, Kathuria 2020) sufficiently dense...

We present an algorithm that computes exact maximum flows and minimum-cost on directed graphs with m edges polynomially bounded integral demands, costs, capacities in 1+ o (1) time. Our builds the flow through a sequence of approximate undirected minimum-ratio cycles, each which is computed processed amortized time using new dynamic graph data structure. framework extends to algorithms running for computing minimize general edge-separable convex functions high accuracy. This gives...

We present an algorithm, which given any m-edge n-vertex directed graph with positive integer capacities at most U computes a maximum s-t flow for vertices s and t in O(m <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4/3+o(1)</sup> xmlns:xlink="http://www.w3.org/1999/xlink">1/3</sup> ) time. This improves upon the previous best running times of xmlns:xlink="http://www.w3.org/1999/xlink">11/8+o(1)</sup>...

In this paper we provide an algorithm for maintaining a (1−є)-approximate maximum flow in dynamic, capacitated graph undergoing edge insertions. Over sequence of m insertions to n-node where every has capacity O(poly(m)) our runs time O(m √n · є−1). To obtain result design dynamic data structures the more general problem detecting when value minimum cost circulation achieves at most F (exactly) given threshold F. and solve thresholded √n). Both algorithms succeed with high probability...

.We give an online algorithm that with high probability computes a \( (\frac{e}{e-1} + o(1) )\Delta\) edge coloring on graph \(G\) maximum degree \(\Delta = \omega (\log n)\) under arrivals against oblivious adversaries, making first progress the conjecture of Bar-Noy, Motwani, and Naor in this general setting. Our is based reducing to matching problem locally treelike graphs, then applying tree recurrence approach for arguing correlation decay.Keywordsedge coloringonline algorithmstree...

We prove that any subset $A \subseteq [3]^n$ with $3^{-n}|A| \ge (\log\log\log\log n)^{-c}$ contains a combinatorial line of length $3$, i.e., $x, y, z \in A$, not all equal, $x_i=y_i=z_i$ or $(x_i,y_i,z_i)=(0,1,2)$ for $i = 1, 2, \dots, n$. This improves on the previous best bound \Omega((\log^* n)^{-1/2})$ [D.H.J. Polymath, Ann. Math. 2012].

We prove local and global inverse theorems for general $3$-wise correlations over pairwise-connected distributions. Let $\mu$ be a distribution $\Sigma \times \Gamma \Phi$ such that the supports of $\mu_{xy}$, $\mu_{xz}$, $\mu_{yz}$ are all connected, let $f: \Sigma^n \to \mathbb{C}$, $g: \Gamma^n $h: \Phi^n \mathbb{C}$ $1$-bounded functions satisfying \[ \left|\mathbb{E}_{(x,y,z) \sim \mu^{\otimes n}}[f(x)g(y)h(z)]\right| \geq \varepsilon. \] In this setting, our theorem asserts there is...

Let $\Sigma_1,\ldots,\Sigma_k$ be finite alphabets, and let $\mu$ a distribution over $\Sigma_1 \times \dots \Sigma_k$ in which the probability of each atom is at least $\alpha$. We prove that if does not admit Abelian embeddings, $f_i: \Sigma_i \to \mathbb{C}$ are $1$-bounded functions (for $i=1,\ldots,k$) such \[ \left|\mathbb{E}_{(x_1,\dots,x_k) \sim \mu^{\otimes n}}\Big[f_1(x_1) f_k(x_k)\Big]\right| \geq \varepsilon, \] then there exists $L\colon \Sigma_1^n\to\mathbb{C}$ degree most $d$...

The upper tail problem in a random graph asks to estimate the probability that number of copies some fixed subgraph an Erdős‐Rényi exceeds its expectation by constant factor. There has been much exciting recent progress on this problem. We study corresponding for hypergraphs, which less is known about large deviation rate. present new phenomena deviations sparse hypergraphs are not seen graphs. conjecture formula rate, is, first order asymptotics log‐probability H k ‐uniform hypergraph This...

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in CONGEST model for solving linear systems graph Laplacian matrices to high accuracy. Our solver has a round complexity of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n^{o(1)}(\sqrt{n}+D))$</tex> , thus almost matches lower bound xmlns:xlink="http://www.w3.org/1999/xlink">$\widetilde{\Omega}(\sqrt{n}+D)$</tex> where...