Events

Abstract: In this talk, we will cover the paper of Svensson and Tarnawski that shows that perfect matching in general (non-bipartite) graphs in is quasi-NC. Similar to the work of Fenner, Gurjar and Thierauf (covered earlier in the reading group), the approach is to derandomize the isolation lemma for the perfect matching polytope by applying weight functions to iteratively restrict to subfaces of the polytope. However, the perfect matching polytope in general graphs is not as well-structured as it is in bipartite graphs. The faces of the polytope no longer correspond to subgraphs and now involve additional tight odd set constraints that need to be dealt with. This makes it so that a cycle with non-zero circulation may still exist in the support of the new face. Additionally, the existence of odd cycles in the graph breaks the cycle counting argument used in the paper of Fenner, Gurjar, Thierauf. We will see how Svensson and Tarnawski deal with these issues in the talk.

Title: Rotation-invariant web bases from hourglass plabic graphs and symmetrized six-vertex configurations

Abstract: Many combinatorial objects with strikingly good enumerative formulae also have remarkable dynamical behavior and underlying algebraic structure. In this talk, we consider the promotion action on certain rectangular tableaux and explain its small, predictable order by reinterpreting promotion as a rotation in disguise. We show how the search for this visual explanation of combinatorial dynamics led to the solution of an algebraic problem involving web bases and a generalization of the six-vertex model of statistical physics. We find that this framework includes several unexpected combinatorial objects of interest: alternating sign matrices, plane partitions, and their symmetry classes (joint with Ashleigh Adams). This talk is based primarily on joint work with Christian Gaetz, Stephan Pfannerer, Oliver Pechenik, and Joshua P. Swanson.

Title: Hypercube decompositions and combinatorial invariance for Kazhdan-Lusztig polynomials

Abstract: Kazhdan-Lusztig polynomials are of foundational importance in geometric representation theory. Yet the Combinatorial Invariance Conjecture, due to Lusztig and to Dyer, suggests that they only depend on the combinatorics of Bruhat order. I'll describe joint work with Grant Barkley in which we adapt the hypercube decompositions introduced by Blundell-Buesing-Davies-Veličković-Williamson to prove this conjecture for Kazhdan-Lusztig R-polynomials in the case of elementary intervals in the symmetric group. This significantly generalizes the main previously known case of the conjecture, that of lower intervals.

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

Title: Determinantal ideals of graphs

Abstract: Let $A$ ($D$) denote the adjacency (distance) matrix of a graph $G$ with $n$ vertices. We define the $k$-th determinantal ideal of $M_X:=diag(x_1,x_2,\ldots ,x_n)+M$ as the ideal generated by all of its minors of size $k\leq n$. If $M=A$, we call this the $k$-th critical ideals of $G$. On the other hand, if $M=D$, we call it the $k$-th distance ideals of $G$. These algebraic objects are related to the spectrum of their corresponding graph matrices, their Smith normal form, and in consequence to their sandpile group for instance. In this talk, we will explore some of the properties and applications of these ideals. 

Title: Concrete analysis of a few aspects of lattice-based cryptography

Abstract: A seminal 2013 paper by Lyubashevsky, Peikert, and Regev proposed using ideal lattices as a foundation for post-quantum cryptography, supported by a polynomial-time security reduction from the approximate Shortest Independent Vectors Problem (SIVP) to the Decision Learning With Errors (DLWE) problem in ideal lattices. In our concrete analysis of this multi-step reduction, we find that the reduction’s tightness gap is so significant that it undermines any meaningful security guarantees. Additionally, we have concerns about the feasibility of the quantum aspect of the reduction in the near future. Moreover, when making the reduction concrete, the approximation factor for the SIVP problem turns out to be much larger than anticipated, suggesting that the approximate SIVP problem may not be hard for the proposed cryptosystem parameters.