We give a strongly polynomial algorithm for minimum cost generalized flow, and as a consequence, for all linear programs with at most two nonzero entries per row, or at most two nonzero entries per column. While strongly polynomial algorithms for the primal and dual feasibility problems have been known for a long time, various combinatorial approaches used for those problems did not seem to carry over to the minimum-cost variant.

Our approach is to show that the ‘subspace layered least squares’ interior point method, an earlier joint work with Allamigeon, Dadush, Loho and Natura requires only a strongly polynomial number of iterations for minimum cost generalized flow. We achieve this by bounding the straight line complexity, introduced in the same paper. The talk will give an overview of the interior point method as well as the combinatorial straight-line complexity analysis for the particular setting. This is joint work with Daniel Dadush, Zhuan Khye Koh, Bento Natura, and Neil Olver.

I will discuss a basic problem in analytic number theory which has appeared recently in my work. This will be a gentle introduction to the Gauss circle problem, hopefully with a discussion of some extensions and applications to understanding L-functions.

I will introduce the Hodge-de-Rham spectral sequence and formulate an algebraic Hodge decomposition theorem. Time permitting, I will sketch Deligne and Illusie’s proof of the Hodge decomposition using positive characteristic methods.

I will introduce various heights on number fields and outline how solving polynomial equations with heights conditions is related to Arakelov geometry and a continuous logic theory called GVF.