We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially-bounded integer costs and capacities. The previous fastest algorithm for this problem is based on interior point methods (IPMs) and works for general sparse graphs in O ( n 1.5 ⋅ poly (log n )) time [Daitch-Spielman, STOC’08]. Intuitively, Ω ( n 1.5 ) is a natural runtime barrier for IPM-based methods, since they require \(\sqrt {n}\) iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested dissection [Lipton-Rose-Tarjan, SINUM’79] and approximate Schur complements [Kyng-Sachdeva, FOCS’16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly \(\sqrt {n}\) update time, resulting in a total runtime of O ( n ⋅ poly (log n )). Our results immediately extend to all families of separable graphs.

We present an algorithm for min-cost flow in graphs with $n$ vertices and $m$ edges, given a tree decomposition of width $τ$ and size $S$, and polynomially bounded, integral edge capacities and costs, running in $\widetilde{O}(m\sqrtτ + S)$ time. This improves upon the previous fastest algorithm in this setting achieved by the bounded-treewidth linear program solver by [Dong-Lee-Ye,21] and [Gu-Song,22], which runs in $\widetilde{O}(m τ^{(ω+1)/2})$ time, where $ω\approx 2.37$ is the matrix multiplication exponent. Our approach leverages recent advances in structured linear program solvers and robust interior point methods (IPM). For general graphs where treewidth is trivially bounded by $n$, the algorithm runs in $\widetilde{O}(m \sqrt n)$ time, which is the best-known result without using the Lee-Sidford barrier or $\ell_1$ IPM, demonstrating the surprising power of robust interior point methods. As a corollary, we obtain a $\widetilde{O}(\operatorname{tw}^3 \cdot m)$ time algorithm to compute a tree decomposition of width $O(\operatorname{tw}\cdot \log(n))$, given a graph with $m$ edges.

In numerical linear algebra, considerable effort has been devoted to obtaining faster algorithms for linear systems whose underlying matrices exhibit structural properties. A prominent success story is the method of generalized nested dissection [Lipton-Rose-Tarjan’79] for separable matrices. On the other hand, the majority of recent developments in the design of efficient linear program (LP) solvers have not leveraged the ideas underlying these faster linear system solvers nor exploited the separable structure of the constraint matrix.

Many fundamental problems in machine learning can be formulated by the convex program \[ \min_{\theta\in \mathbb{R}^d}\ \sum_{i=1}^{n}f_{i}(\theta), \]where each $f_i$ is a convex, Lipschitz function supported on a subset of $d_i$ coordinates of $\theta$. One common approach to this problem, exemplified by stochastic gradient descent, involves sampling one $f_i$ term at every iteration to make progress. This approach crucially relies on a notion of uniformity across the $f_i$'s, formally captured by their condition number. In this work, we give an algorithm that minimizes the above convex formulation to $\epsilon$-accuracy in $\widetilde{O}(\sum_{i=1}^n d_i \log (1 /\epsilon))$ gradient computations, with no assumptions on the condition number. The previous best algorithm independent of the condition number is the standard cutting plane method, which requires $O(nd \log (1/\epsilon))$ gradient computations. As a corollary, we improve upon the evaluation oracle complexity for decomposable submodular minimization by [Axiotis, Karczmarz, Mukherjee, Sankowski and Vladu, ICML 2021]. Our main technical contribution is an adaptive procedure to select an $f_i$ term at every iteration via a novel combination of cutting-plane and interior-point methods.

We present a nearly-linear time algorithm for finding a minimum-cost flow in planar graphs with polynomially bounded integer costs and capacities. The previous fastest algorithm for this problem was based on interior point methods (IPMs) and worked for general sparse graphs in O(n1.5 poly(log n)) time [Daitch-Spielman, STOC'08]. Intuitively, Ω(n1.5) is a natural runtime barrier for IPM based methods, since they require iterations, each routing a possibly-dense electrical flow. To break this barrier, we develop a new implicit representation for flows based on generalized nested-dissection [Lipton-Rose-Tarjan, JSTOR'79] and approximate Schur complements [Kyng-Sachdeva, FOCS'16]. This implicit representation permits us to design a data structure to route an electrical flow with sparse demands in roughly update time, resulting in a total running time of O(n · poly(log n)). Our results immediately extend to all families of separable graphs.

Arising from structural graph theory, treewidth has become a focus of study in fixed-parameter tractable algorithms. Many NP-hard problems are known to be solvable in O(n · 2O(τ)) time, where τ is the treewidth of the input graph. Analogously, many problems in P should be solvable in O(n · τO(1)) time; however, due to the lack of appropriate tools, only a few such results are currently known. In our paper, we show this holds for linear programs: Given a linear program of the form minAx=b,ℓ ≤ x≤ u c⊤ x whose dual graph GA has treewidth τ, and a corresponding width-τ tree decomposition, we show how to solve it in time

The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Primal-Dual Circle Packing Theorem for 3-connected planar graphs. The existence of these representations has widespread applications in theoretical computer science and mathematics; however, the algorithmic aspect has received relatively little attention. In this work, we present an algorithm based on convex optimization for computing a primal-dual circle packing representation of maximal planar graphs, i.e. triangulations. This in turn gives an algorithm for computing a circle packing representation of any planar graph. Both take Õ(n log(R/ε)) expected run-time to produce a solution that is ϵ close to a true representation, where R is the ratio between the maximum and minimum circle radius in the true representation.

The re-capturing of video content poses significant challenges to algorithms in the fields of video forensics, watermarking, and near-duplicate detection. Using a camera to record a video from a display introduces a variety of artifacts, such as geometric distortions, luminance transformations, and temporal aliasing. A deep understanding of the causes and effects of such phenomena is required for their simulation, and for making the affected algorithms more robust. In this paper, we provide a detailed model of the temporal effects in re-captured video. Such effects typically result in the re-captured frames being a blend of the original video's source frames, where the specific blend ratios are difficult to predict. Our proposed parametric model captures the temporal artifacts introduced by interactions between the video renderer, display device, and camera. The validity of our model is demonstrated through experiments with real re-captured videos containing specially marked frames.