Events

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: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:Erdős-Pósa theorem for matroids

Abstract: We will look at an analogue theorem of the classical Erdős-Pósa Theorem. We prove a $GF(q)$-representable matroid analogue of Robertson and Seymour's theorem that planar graphs have an Erdős-Pósa property. Given a matroid $N$, we prove that for every matroid $M$ with bounded branch width, $M$ either contains $r$ skew copies of $N$, or there is a small perturbation of $M$ that doesn't contain $N$ as a minor.

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: The degrees of Stiefel Manifolds

Abstract:

The set of orthonormal bases for k-planes in R^n is cut out by the equations X*X^T = I
where X is a k x n matrix of variables and I is k x k identity. This space, known as the Stiefel manifold St(k,n), generalizes the orthogonal group and can be realized as the homogeneous space O(n)/O(n-k). Its algebraic closure
gives a complex affine variety, and thus, it has a degree.

I will discuss our derivation of these degrees. Extending 2017 work on the degrees of special orthogonal groups, joint work with Fulvio Gesmundo gives a combinatorial formula in terms of non-intersecting lattice paths.
This result relies on representation theory, commutative algebra, Ehrhart theory, polyhedral geometry, and enumerative combinatorics.

I will conclude with some open problems inspired by these objects.

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

Abstract: In this talk, we consider a linear algebraic object known as a tridiagonal pair which arises naturally in the context of Q-polynomial distance-regular graphs. We will focus on a special class of tridiagonal pairs said to have Racah type. Given a tridiagonal pair of Racah type, we associate with it several linear transformations which act on the underlying vector space in an attractive manner and discuss their relationships with one another. In an earlier work, we introduced the double lowering operator Ψ for a tridiagonal pair. In this talk, we will explore this double lowering map further under the assumption that our tridiagonal pair has Racah type and will use the double lowering map to obtain new relations involving the operators associated with two oriented versions of our tridiagonal pair.

Abstract: We give an overview of a new Legendre-based signature scheme called Loquat that is friendly for SNARK-based applications. While we primarily focus on the constructive applications, we also discuss the historical context, security and cryptanalysis of the Legendre PRF. The primary content of the talk is based on ia.cr/2024/868.