Seminar

Title: Research in Applications

Abstract: In this talk I will present my personal experiences in doing research involving applications. I will go over some of my work, presenting some of the key aspects that are involved, and trying to take stock of a few lessons learned.

Title: Monomial ideals, Galois closures, and Hilbert schemes of points

Abstract: Manjul Bhargava and the speaker introduced a functorial Galois closure operation for finite-rank ring extensions, generalizing constructions of Grothendieck and Katz-Mazur. In this talk, we use Galois closures to construct new components of Hilbert schemes of points, which are fundamental objects in algebraic geometry whose component structure is largely mysterious. We answer a 35 year old open problem posed by Iarrobino by constructing an infinite family of low dimensional components. This talk is based on joint work with Andrew Staal. No prior knowledge of Hilbert schemes will be assumed.

Title: L-systems and the Lovasz number

Abstract: For positive integers n and k, an L-system is a collection of k-uniform subsets of a set of size n whose pairwise intersection sizes all lie in in the set L. The maximum size of an L-system is equal to the independence number of a certain union of graphs in the Johnson scheme. The Lovasz number is a semidefinite programming approximation of the independence number of a graph. In this talk, we survey the relationship between the maximum size of an L-system and the Lovasz number, illustrating examples both where the Lovasz number is a good approximation and where it is a bad approximation.

Title: Error bounds for conic feasibility problems: case studies on the exponential cone

Abstract: Conic feasibility problems naturally arise from linear conic programming problems. An understanding of error bounds for these problems is instrumental in the design of termination criteria for conic solvers and the study of convergence rate of algorithms.

Title: Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse

Abstract: I will present the online algorithms for unrelated-machine load balancing problem with recourse.  First, we shall present a (2+\epsilon)-competitive algorithm for the problem with O_\epsilon(\log n) amortized recourse per job.

Title: On the complexity of quantum partition functions

Abstract: Quantum complexity theory has been intertwined with the study of quantum many-body systems ever since Kitaev's insight that computing their ground energies is an intractable quantum constraint satisfaction problem that is complete for a quantum generalization of NP.

Title: Breaking the Supersingular Isogeny Diffie-Hellman protocol

Abstract: Finding an explicit isogeny between two given isogenous elliptic curves over a finite field is considered a hard problem, even for quantum computers.

Title: Generalized Modular String Averaged Procedure and Its Applications to Iterative Methods

Abstract: A modular string averaging procedure (MSA, for short) for a finite number of operators  was first introduced by Reich and Zalas in 2016. The MSA concept provides a flexible  algorithmic framework for solving various feasibility problems such as common fixed point and convex feasibility problems.

Title: Eigenvalues for stochastic matrices with a prescribed stationary distribution

Abstract: A square nonnegative matrix T is called stochastic if all of its row sums are equal to 1. Under mild conditions, it turns out that there is a positive row vector w^T (called the stationary distribution for T) whose entries sum to 1 such that the powers of T converge to the outer product of w^T with the all-ones vector. Further, the nature of that convergence is governed by the eigenvalues of T.

In this talk we explore how the stationary distribution for a stochastic matrix exerts an influence on the corresponding eigenvalues.

Title: Bounding the extended complexity of the stable set polytope on perfect graphs

Abstract: This week we will study the extension complexity of the stable set polytope for perfect graphs. More than 40 years ago, Grötschel et al. gave an algorithm to find maximal weight stable sets on perfect graphs based on a compact semidefinite extension. However, whether there is a compact linear extension is still an open problem.