Events

Tubings of rooted trees and resurgence

Abstract:

I will explain about how tubings of rooted trees can solve Dyson-Schwinger equations and how, when the Mellin transform is a reciprocal of a polynomial with rational roots, then one can extend the notion of, tubings to label the tubes with letters from some alphabets and from there just by standard generatingfunctionology obtain a system of differential equations that is perfectly suited to resurgent analysis.

Joint work with Michael Borinsky and Gerald Dunne, arXiv:2408.15883

There will be NO pre-seminar on September 19.

Title: LP based approximation algorithm for an stochastic matching problem

Abstract: Consider the random graph model where each edge e has a fixed weight w_e and it is independently present in the graph with probability p_e​. Given these probabilities, we want to construct a maximum weight matching in the graph. One can only determine if an edge is present by querying it, and if an edge is present, it must be irrevocably included in the matching. Additionally, each vertex i can be queried no more than t_i times. The goal is to device an adaptive policy (algorithm) to query the edges of the graph one by one in order to maximize the expected weight of the matching.

In this talk we present an elegant LP-based constant-factor approximation algorithm with respect to the optimal adaptive policy for the problem.

This is one of the results due to Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra, in their paper "When LP is the Cure for your Matching Woes" from 2011.

A strongly polynomial algorithm for linear programs with at most two non-zero entries per row or column.

Abstract:We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two non-zero entries per column. Primal and dual feasibility were shown by Megiddo (SICOMP '83) and Végh (MOR '17) respectively. Our result can be viewed as progress towards understanding whether all linear programs can be solved in strongly polynomial time, also referred to as Smale's 9th problem. Our approach is based on the recent primal-dual interior point method (IPM) due to Allamigeon, Dadush, Loho, Natura and Végh (FOCS '22). The number of iterations needed by the IPM is bounded, up to a polynomial factor in the number of inequalities, by the straight line complexity of the central path. Roughly speaking, this is the minimum number of pieces of any piecewise linear curve that multiplicatively approximates the central path. As our main contribution, we show that the straight line complexity of any minimum cost generalized flow instance is polynomial in the number of arcs and vertices. By applying a reduction of Hochbaum (ORL '04), the same bound applies to any linear program with at most two non-zeros per column or per row. To be able to run the IPM, one requires a suitable initial point. For this purpose, we develop a novel multistage approach, where each stage can be solved in strongly polynomial time given the result of the previous stage. Beyond this, substantial work is needed to ensure that the bit complexity of each iterate remains bounded during the execution of the algorithm. For this purpose, we show that one can maintain a representation of the iterates as a low complexity convex combination of vertices. Our approach is black-box and can be applied to any log-barrier path following method. 

Bento Natura is an Assistant Professor in Industrial Engineering and Operations Research (IEOR) at Columbia University. He spent two years as a Postdoctoral Fellow at Georgia Tech, Brown University, and UC Berkeley. Prior to that, he obtained his PhD in Mathematics from the London School of Economics.

His research interests are focused on the areas of algorithms, optimization, and game theory, with a special emphasis on the theory of linear programming.

Approximately Counting Flows via Generating Function Optimization

Abstract: In this talk, we will present recent new lower bounds on the number of non-negative integer flows on a directed acyclic graph with specified total vertex flows (or equivalently, the number of lattice points of a given flow polytope, or the coefficients of the A-type Kostant partition function). We will also give a sketch of the proof, which involves three main parts: (1) prove a certain log-concavity property of the associated multivariate generating function, (2) prove bounds on the coefficients in terms of an associated optimization problem, and (3) dualize the optimization problem to obtain the desired lower bounds. If time permits, we will also briefly discuss other applications of this technique, including to approximating Kostka numbers and to the traveling salesperson problem. Joint work with Alejandro Morales, and with Petter Brändén and Igor Pak.

There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1pm,