Seminar

Title:PRISM: Simple And Compact Identification and Signatures From Large Prime Degree Isogenies

Abstract: The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. 

Title:Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection

Abstract: For any epsilon > 0, we prove that k-Dimensional Matching is hard to approximate within a factor of k/(12 + epsilon) for large k unless NP \subseteq BPP. Listed in Karp's 21 NP-complete problems, k-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: k-Set Packing, k-Matroid Intersection, and Matroid k-Parity. For all the aforementioned problems, the best known lower bound was an Omega(k /log(k))-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieved an approximation of O(k). Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties. 

Title: Structure of Eigenvectors of Graphs 

Abstract: Let G be a graph on n vertices with characteristic polynomial φ_G(λ). A graph is said to be irreducible if the characteristic polynomial of its

Title:Non-uniform Kahn-Kalai: the fractional version, the dual and its power in capturing “thresholds"

Abstract:There have been several advancements in the study of thresholds in recent years, including the groundbreaking proof of the Kahn-Kalai conjecture by Park and Pham. B. Park and Vondrák also later extended this work in the non-uniform setting (where we allow different edges to have different probabilities, unlike G(n, p)). In many concrete applications of determining thresholds in G(n, p), “spread" is used to prove the 1-statement. In this talk, we extend the notion of “spread" in the non-uniform setting to test its power in capturing the “threshold". This talk is based on joint work with Jane Gao.

Title: Algebraic and enumerative combinatorics seminar

Abstract:

Permuted-basement Macdonald polynomials E_α^σ(x_1, ..., x_n; q, t) are nonsymmetric generalizations of symmetric Macdonald polynomials indexed by a composition α and a permutation σ. They can be described combinatorially as generating functions over augmented fillings of shape α and basement σ.

We construct deterministic and probabilistic bijections on fillings that prove identities relating

E_α^σ, E_α^{σ s_i}, E_{s_i α}^σ, and E_{s_i α}^{σ s_i}.

These identities arise from two operations on the shape and basement: swapping adjacent parts of the shape, which expands

E_α^σ intoE_{s_i α}^σ and E_{s_i α}^{σ s_i}; and swapping adjacent basement entries,

which gives E_α^σ = E_α^{σ s_i} when α_i = α_{i+1}.

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

Title:Enhancing Anamorphic Cryptography

Abstract: Anamorphic cryptography (Persiano, Phan, and Yung, Eurocrypt 2022) allows users who share a “double key” to hide encrypted messages in ciphertexts and signatures to allow covert communication under a hypothetical “dictator” who can monitor all communication or force parties to give up their cryptographic keys in order to check for compliance.

Title: Fast quantum state transfer on paths via localized eigenvectors

Abstract: 

Title:The Heron-Rota-Welsh conjecture via Lorentzian polynomials

Abstract:The Heron-Rota-Welsh conjecture asserts that the characteristic polynomial of a matroid has log-concave coefficients. This conjecture was open since the 1970s until it was proven by Adiprasito, Huh, and Katz in 2018 using their newly developed combinatorial Hodge theory. Their proof was groundbreaking, but rather complicated. In this talk, we will give a proof of this fact using Lorentzian polynomials, which otherwise will use nothing more than basic theory of matroids, linear algebra, and convexity.

Title:Almost Regular Matroids

Abstract: Regular matroids form an important and extensively studied class of matroids and have numerous known descriptions and characterizations. In the 1980s, Truemper gave a constructive description of the related class of almost regular matroids: non-regular matroids $M$ such that for every element $e$ of $M$ either $M/e$ or $M\backslash e$ is regular. In this talk, we present a description of almost regular matroids in terms of grafts. A consequence of this description is that almost regular matroids have bounded complexity. We outline some of the proof ideas after introducing the necessary background.

Title: Generalized Abelian Complexities for Pisot-Type Substitutive Sequences

Abstract: Two finite words are said to be abelian equivalent if one is a permutation of the letters of the other. For an infinite word, one can investigate the associated complexity function, called Abelian complexity, which is a classical object of study in combinatorics on words. In particular, many works study the abelian complexity of automatic sequences, where a longstanding conjecture states that the abelian complexity of an automatic sequence is a regular sequence. We have studied when the abelian complexity can be computed efficiently, in particular using the theorem prover Walnut. To this end, we study words that are fixed points of Pisot-type substitution and prove that these words satisfy the conjecture. If time permits, I will present k-abelian complexities, which are intermediate complexities between the abelian complexity and the factor complexity. I will also explain how our results can be extended to these
complexities and how we can obtain a two-dimensional linear representation of some examples. This talk is based on joint work with J-M Couvreur, M. Delacourt, N. Ollinger, J. Shallit, and M. Stipulanti (arXiv: 2504.13584).

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