Events

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.

Ramsey numbers and configurations of finite polar spaces

Abstract: This talk is on some joint work with Anurag Bishnoi and Ferdinand Ihringer, about a simple observation on how Ramsey theory relates to certain induced subgraphs of collinearity graphs arising from finite polar spaces; the natural geometries for the finite simple groups of classical Lie type

A combinatorial proof of an identity involving Eulerian numbers

Abstract:In 2009, Brenti and Welker studied the Veronese construction for formal  power series which was motivated by the corresponding construction for  graded algebras. As a corollary of their algebraic computations, they  discovered an identity for the coefficients of the Eulerian polynomials.  The authors asked for a combinatorial proof of this identity given that  all of its ingredients are enumerative in nature. In this talk I will present one such combinatorial proof. I will gladly do a pre-seminar with the motivation and preliminaries for the talk!

Title: Stable Matchings and a Matroid Generalization

Abstract: Today we'll continue our theme of matchings and talk about stable matchings! We won't assume much previous experience with stable matchings, and we will (re)introduce what they are. After, we will talk about classic results and some more recent approximations for generalizations of the problem. In the classic stable matching problem, we are given a bipartite graph and for each vertex we are given a list of strict preferences over other vertices. The goal is to find a "stable" matching, where no two vertices would prefer being matched to other vertices. This can be accomplished using the classic Gale-Shapley algorithm, which we will review. We will also consider when ties and indifferences can be present in the list of preferences. With such preferences, the problem becomes APX-Hard. However, McDermid showed it is possible to achieve a 1.5 approximation. We will talk about this, and comment on a recent generalization to matroids from Csaji, Kiraly, and Yokoi.

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.

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.

Title: Diophantine tuples, graphs, and additive combinatorics

Abstract: In this talk, we investigate the multiplicative structure of a shifted multiplicative subgroup and its connections with additive combinatorics and the theory of Diophantine tuples and Diophantine graphs. First, we show that if a nontrivial shift of a multiplicative subgroup $G$ contains a product set $AB$, then $|A||B|$ is essentially bounded by $|G|$, refining a well-known consequence of a classical result by Vinogradov. Second, we provide a sharper upper bound of $M_k(n)$, or the clique number of Diophantine graphs, which is the largest size of a set such that each pairwise product of its elements is $n$ less than a $k$-th power, refining the recent result of Dixit, Kim, and Murty.  One main ingredient in our proof is the first non-trivial upper bound on the maximum size of a generalized Diophantine tuple over a finite field. In addition, we determine the maximum size of an infinite family of generalized Diophantine tuples over finite fields with square order, which is of independent interest.  

We also present a significant progress towards a conjecture of S\'{a}rk\"{o}zy on the multiplicative decompositions of shifted multiplicative subgroups. In particular, we prove that for almost all primes $p$, the set $\{x^2-1: x \in \F_p^*\} \setminus \{0\}$ cannot be decomposed as the product of two sets in $\F_p$ non-trivially.

Title: Non-measurable colourings avoiding large distances

Abstract: "In 1983, F{\"u}rstenberg, Katznelson, and Weiss proved that for every finite measurable colouring of the plane, there exists a $d_0$ such that for every $d \ge d_0$ there is a monochromatic pair of points at distance $d$. In contrast to this, we show that there is a finite colouring avoiding arbitrarily large distances.

Joint work with Rutger Campbell."