Georgia Institute of Technology College of Sciences

In recent years, the theories of Lorentzian polynomials and combinatorial Hodge theory have been developed and utilized to resolve long-standing conjectures in matroid theory, related to log-concavity inequalities and sampling algorithms. The overarching idea in these theories is to extract the conjectured results from basic eigenvalue bounds on certain natural matrices associated to matroids. Since then, Lorentzian polynomials have been generalized beyond matroids to simplicial complexes of various types, implying old and new results on various combinatorial structures such as linear extensions of posets. That said, many questions remain open. In this talk, we will describe this generalized theory and discuss how it can be used to prove various combinatorial results. No knowledge of matroid theory will be assumed. Joint work with Kasper Lindberg and Shayan Oveis Gharan, and also with Petter Brändén.

Giroux torsion is an important class of contact structures on a neighborhood of a torus, which is known to obstruct symplectic fillability. Ghiggini conjectured that half Giroux torsion along a separating torus always results in a vanishing Heegaard Floer contact invariant hence also obstructs fillability. In this talk, we present a counterexample to that conjecture. Our main tool is a bordered contact invariant, which enables efficient computation of the contact invariant.

Let $LC_n$ be the length of the longest common subsequences of two independent random words whose letters are taken  

in a finite alphabet and when the alphabet is totally ordered, let $LCI_n$ be the length of the longest common and increasing subsequences of the words.   Results on the asymptotic means, variances and limiting laws of these well known random objects will be described and compared.  

We consider one of the most basic high-dimensional testing problems: that of detecting the presence of a rank-1 "spike" in a random Gaussian (GOE) matrix. When the spike has structure such as sparsity, inherent statistical-computational tradeoffs are expected. I will discuss some precise results about the computational complexity, arguing that the so-called "linear spectral statistics" achieve the best possible tradeoff between type I & II errors among all polynomial-time algorithms, even though an exponential-time algorithm can do better. This is based on https://arxiv.org/abs/2311.00289 with Ankur Moitra which uses a version of the low-degree polynomial heuristic, as well as forthcoming work with Ansh Nagda which gives a stronger form of reduction-based hardness.