Events

Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams 

Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs.

Title: The Chambolle-Pock algorithm revisited: splitting operator and its range with applications

Abstract: Primal-dual hybrid gradient (PDHG) is a first-order method for saddle-point problems and convex programming introduced by Chambolle and Pock. Recently, Applegate et al. analyzed the behavior of PDHG when applied to an infeasible or unbounded instance of linear programming, and in particular, showed that PDHG is able to diagnose these conditions.

Title: Algorithmic Tools for Congressional Districting: Fairness via Analytics

Abstract: The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics.

Title: Hypergraph Matchings Avoiding Forbidden Submatchings

Abstract: We overview a general theory for finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of forbidden submatchings (which we view as a hypergraph H where V(H)=E(G)).

Title: Diagonal coefficients, graph invariants with the symmetries of Feynman integrals, and the proof of the c_2 completion conjecture

Abstract: In a scalar field theory the contribution of a Feynman diagram to the beta function of the theory, the Feynman period, can be written as an integral in terms of the (dual) Kirchhoff polynomial of the graph.

Title: Wires, bits, and the cost of sorting

Abstract: How hard is it to sort a list of n integers? A basic course on algorithms says it's O(n log n) time, but what if the list is enormous - so big you would need to cover the surface of the moon just to store it?

Title: Bivariate P-polynomial Association Schemes on the Fibers of Uniform Posets

Abstract: Orthogonal polynomials emerging in the context of P- and Q-polynomial association schemes are known to reside within the Askey-scheme. This relationship forms a bridge between algebraic combinatorics and the study of special functions, yielding significant benefits for both fields. Recent research has introduced multivariate generalizations of P- and Q-polynomial association schemes and provided numerous examples. This development aims notably to deepen our understanding of multivariate analogues of Askey-Wilson polynomials. In this talk, we will review this generalization, its connection to m-distance-regular graphs, and an algebraic combinatorial structure known as a "uniform poset," from which many examples of bivariate schemes appear to originate.

There will be a social starting at 1:00pm

Title: Notation of Total Dual Integrality for Semidefinite Programming

Speaker: Mehrdad Sohrabi

Abstract:

Total dual integrality (TDI) plays a crucial role in integer programming and polyhedral combinatorics, with applications in network flows, matching, and more. Semidefinite programming is an instance of conic optimization that generalizes linear programming. In this talk, we will discuss the notion of total dual integrality for semidefinite programming, first introduced by M. K. Carli Silva and L. Tuncel. We will also present the new results we obtained during this semester.

Title: Formal Method for Verifying the Security Cryptosystems

Speaker: Zhisu Wang

Abstract:

CryptoVerif is a security protocol verifier producing proofs presented as sequences of games, like those manually written by cryptographers. We introduce the basic syntax of CryptoVerif with an example of proving a simple primitive. Then we show the attempts to apply this tool on more complex cryptographic protocols.

Title: Measures of Robustness and Efficiency of Convex Optimization Algorithms

Speaker: Jessica Ding

Abstract:

Interior point method solvers have proven to be an effective tool for solving linear and non-linear convex optimization problems. In this talk I will introduce some measures of robustness and efficiency of convex optimization algorithms as well as intuition behind them. We will learn about the property of ill-poisedness and how it influences the efficiency and correctness of solvers. I will also show some of the results from the experiments we ran over the term.

Sum of squares of positive eigenvalues

The spectral Turán theorem says that if a graph has largest eigenvalue $\lambda_1$, $m$ edges and clique number $\omega$, then $\lambda_1^2 \leq 2m (1-\frac{1}{\omega})$. This result implies the classical Turán bound $m \leq (1-\frac{1}{\omega})\frac{n^2}{2}$.
In this talk, we present the proof of the Wocjan, Elphick and Anekstein conjecture in which, in the spectral Turán bound, the square of the first eigenvalue is replaced by the sum of the squares of the positive eigenvalues and the clique number is replaced by the vector chromatic number. 
We will also present recent progress towards a conjecture by Bollobás and Nikiforov in which, in the spectral Turán bound, the square of the first eigenvalue is replaced by the sum of the squares of the two largest eigenvalues. This is joint work with Gabriel Coutinho and Shengtong Zhang.

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.