Events

Abstract:  Discretizable Distance Geometry Problems (DDGP) consist in a subclass of Distance Geometry Problems (DGP) where the search space can be discretized and reduced to a binary tree. Such problems can be tackled by applying a Branch-and- Prune algorithm (BP), which is able to perform an exhaustive enumeration of the solution set. 

Abstract:  Exceptional collections are a powerful tool for understanding the derived category of coherent sheaves on algebraic varieties, with applications in commutative algebra, birational geometry, and mirror symmetry. While the existence of exceptional collections is known for classical varieties such as Grassmannians and flag varieties, constructing explicit collections for toric varieties presents challenges in combinatorial algebraic geometry. In this talk I will describe a computational approach to constructing full strong exceptional collections consisting of complexes of line bundles for toric varieties. No background in derived categories is assumed.

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

Abstract:  The study of matroid tensor products dates back to the 1970s, extending the tensor operation from linear algebra to the combinatorial setting. While any two matroids representable over the same field admit a tensor product via the Kronecker product of matrices, Las Vergnas showed that such products do not exist for matroids in general, leaving the area underexplored. In this work, we utilize this operation to study skew-representability — representation over division rings that need not be commutative — by proving that a matroid is skew-representable if and only if it admits iterated tensor products with specific test matroids. A key consequence is the existence of algorithmic certificates for non-representability. We further show that every rank-3 matroid admits a tensor product with any uniform matroid, constructing the unique freest such product. Finally, we demonstrate the power of this framework by deriving the first known linear rank inequality for (folded skew-)representable matroids that is independent of the common information property. 

Abstract:  Modern secure communication systems, such as iMessage, WhatsApp, and Signal include intricate mechanisms that aim to achieve very strong security properties. These mechanisms typically involve continuously merging fresh secrets into the keying material that is used to encrypt messages during communications. In the literature, these mechanisms have been proven to achieve forms of Post-Compromise Security (PCS): the ability to provide communication security even if the full state of a party was compromised some time in the past. However, recent work has shown these proofs cannot be transferred to the end-user level, possibly because of usability concerns. This has raised the question of whether end-users can actually obtain PCS or not, and under which conditions.

Abstract: Tensor integrals are the generating functions of triangulations of pseudo-manifolds. Such triangulations are constructed by gluing simplices along facets. These generating functions satisfy an infinite system of recursive equations called the Dyson-Schwinger equations, derived by reclusively gluing together triangulations. Such integrals also satisfy positivity constraints. By combining the Dyson-Schwinger equations and positivity constraints in a process called bootstrapping we are able to deduce known results for the generating functions of certain classes of triangulations as well as find new explicit formulae. This talk is based on joint work with Carlos I. Perez-Sanchez and Brayden Smith.

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

Abstract: A (t,n)-threshold signature scheme splits a signing key among "n" participants so that any "t" can jointly produce a valid signature under a single public key, while fewer than "t" cannot. There are three common types of threshold signature schemes: (i) Robust schemes, which guarantee signature production provided at least "t" parties are honest; (ii) Identifiable-abort schemes, which may fail to produce a signature but expose at least one misbehaving signer; and (iii) Simple schemes, which guarantee neither robustness nor identifiable abort, but output a valid signature when "t" honest participants collaborate without deviating from the protocol.

Motivated by NIST's recent emphasis on post-quantum multiparty and threshold designs, this talk presents a new approach to centralized, lattice-based (t,n)-threshold signatures. We first construct a (t,n)-threshold one-time signature and then upgrade it to a many-time scheme by combining it with a long-term signature so that all threshold signatures verify under a single public key.

Abstract:  In this talk, we demonstrate a connection between log-concavity statements and sampling algorithms via high-dimensional expanders and Lorentzian polynomials. To do this, we first discuss two conjectures which were resolved about 5-10 years ago: one on the log-concavity of independent sets of matroids (due to Brändén-Huh and Anari-Liu-Oveis Gharan-Vinzant), and one on efficiently sampling bases of matroids (due to Anari-Liu-Oveis Gharan-Vinzant). From there we will present some new results on generalized graph colorings which extend these and other previous results. In particular, we will discuss how this can be used to obtain log-concavity statements and sampling algorithms for linear extensions of posets. Joint work with Kasper Lindberg and Shayan Oveis Gharan.

Abstract: Suppose that you are given an ordering of the elements of a $k$-connected matroid, and you want to remove the elements one at a time, in the given order, keeping the intermediate matroids as highly connected as possible. How much connectivity can you keep?

Abstract: For all positive integers l and r, we determine the maximum number of elements of a simple rank-r positroid without the rank-2 uniform matroid U(2, l+2) as a minor, and characterize the matroids with the maximum number of elements. This result continues a long line of research into upper bounds on the number of elements of matroids from various classes that forbid U(2, l+2) as a minor, including works of Kung, of Geelen–Nelson, and of Geelen–Nelson–Walsh. This is the first paper to study positroids in this context, and it suggests methods to study similar problems for other classes of matroids, such as gammoids or base-orderable matroids. This project is based on joint work with Zach Walsh.

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

Abstract:  FrodoKEM is a lattice-based Key Encapsulation Mechanism (KEM) based on unstructured lattices. From a security point of view this makes it a conservative option to achieve post-quantum security, hence why it is favored over the NIST winners by several European authorities (e.g., German BSI and French ANSSI). Relying on unstructured instead of structured lattices (e.g., CRYSTALS-Kyber) comes at the cost of additional memory usage, which is particularly critical for embedded security applications such as smart cards. For example, prior FrodoKEM-640 implementations (using AES) on Cortex-M4 require more than 80 kB of stack making it impossible to run on embedded systems. In this work, we explore several stack reduction strategies and the resulting time versus memory trade-offs. Concretely, we reduce the stack consumption of FrodoKEM by a factor 2–3× compared to the smallest known implementations with almost no impact on performance. We also present various time-memory trade-offs going as low as 8 kB for all AES parameter sets, and below 4 kB for FrodoKEM-640. By introducing a minor tweak to the FrodoKEM specifications, we additionally reduce the stack consumption down to 8 kB for all the SHAKE versions. As a result, this work enables FrodoKEM on embedded systems.