Algebra and Discrete Mathematics Seminar

Recording: https://clemson.zoom.us/rec/share/AEVZRD6b_d-RXV-IH4NRCJe_XGu1oilPsAwNxXEpQXA-R-WTVy5s2imZkuRwqlUK.dV-M9a7KoVFsuKD6 

Lattice reduction algorithms have received much attention in recent years due to their relevance in cryptography. In this talk, we will discuss some of the recent developments on enumeration-based lattice reduction algorithms.

First, we will discuss a lattice reduction algorithm that achieves root Hermite factor k^(1/(2k)) in time k^(k/8 + o(k)) and polynomial memory. This improves the previously best known enumeration-based algorithms which achieve the same quality, but in time k^(k/(2e) +o(k)). The main idea is to conduct the preprocessing in a larger dimension than the enumerate dimension. Second, we discuss the usage of approximate enumeration oracles in BKZ, together with extended preprocessing ideas. In the end, we will illustrate some simulated results to demonstrate their practical behavior.

This talk is based on the following joint work:

M. R. Albrecht, S. Bai, P. A. Fouque, P. Kirchner, D. Stehlé, W. Wen: Faster Enumeration-Based Lattice Reduction: Root Hermite Factor k^(1/(2k)) Time k^(k/8+o(k)). CRYPTO (2) 2020: 186-212.

M. R. Albrecht, S. Bai, J. Li, J. Rowell: Lattice Reduction with Approximate Enumeration Oracles – Practical Algorithms and Concrete Performance. CRYPTO (2) 2021: 732-759.

Recording: https://clemson.zoom.us/rec/share/dXIdA2oeXbXxHc36-btMek6w-UtSJWJE7tXcSYZHInTFplavHpt2aRr9WsyEXZ7w.6hJmraIuU4-NEzAd 

Matrix multiplication is, oftentimes, the most expensive computational task in an algorithm. It is the computational bottleneck for training many of the now well-celebrated learning algorithms, for example. To speed up the algorithm, the data can be distributed on many machines to perform the computations in parallel. This sharing of the data, however, raises security concerns when the data is sensitive and has to remain private, such as financial or medical data. Secure distributed matrix multiplication (SDMM) studies how to parallelize matrix multiplication while keeping the data secure.

In this talk, we present a combinatorial tool, called the degree table, and show how to utilize it to construct codes for SDMM which are currently the best performing for their parameters. I will also show lower bounds for this technique and characterize the total time complexity for SDMM codes, showing that if the parameters of the code are not chosen carefully, the total time might be larger than simply performing the computation locally.

Recording: https://clemson.zoom.us/rec/share/Xg_43QJTi0NdLfBj2hcO_xZHWeggXgUJLFAdBEMBudYqapz0FcQbX4xfkmLz6K2P.lHWM0cHvnGur2_8c

Let G be a finite simple graph. This talk investigates the properties of symbolic powers of cover ideals associated to G. The results begin with combinatorially changing a given graph by whiskering (introducing a degree one vertex) a cycle cover of the graph. We show that this process forces all symbolic powers of the cover ideal J(G) to be Koszul or, equivalently, componentwise linear. We follow this result with a method of gluing two graphs, with Koszul cover ideals, together to obtain a new graph whose cover ideal, and all its symbolic powers, are Koszul. 

We then move to studying a spanning bipartite subgraph, B_G, of G. We first give conditions on J(G) which give that symbolic power J(G)^{(s)} is not componentwise linear for s>2. We then use this result and  B_G to give necessary and sufficient conditions on J(G) such that J(G)^{(s)} is componentwise linear for all s>1. In particular when G is a graph such that G\ N[A] has a simplicial vertex for any independent set A, or when G is a bipartite graph. 

This is joint work with Yan Gu, Tài Hà, and S. Selvaraja.

Recording: https://clemson.zoom.us/rec/play/sapiFtf9Z2RlthV4SlsH7HquQDvavzvkO_O0LOr40KeLzRlo_jQp8I6mlVcN7461XWxpx-nTKGwNNLuH.d93sFx8ztontOARc?continueMode=true

Let A be a polynomial ring and I₁,…, I_r be a collection of ideals in A. The multi-Rees algebra R( I₁,…, I_r) of this collection of ideals encode many algebraic properties of these ideals, their products, and powers. Additionally, the multi-Rees algebra  R( I₁,…, I_r) arise in successive blowing up of Spec A at the subschemes defined by I₁,…,I_r. Due to this connection, Rees and multi-Rees algebras are also called blow-up algebras in the literature.

In this talk, we will focus on Rees and multi-Rees algebras of strongly stable ideals. In particular, we will discuss the Koszulness of these algebras through a systematic study of these objects via three parameters: the number of ideals in the collection, the number of Borel generators of each ideal, and the degrees of Borel generators. In our study, we utilize combinatorial objects such as fiber graphs to detect Gröbner bases and Koszulness of these algebras. This talk is based on a joint work with Kuei-Nuan Lin and Gabriel Sosa.

Recording link: https://clemson.zoom.us/rec/share/5mix_qR6bjmzWc5PvPibZzrKzw678Y1cJAFf6XMmvcwkbUT7S9EcnN3pOBmsnYwZ.Gm2IvqZ2G1vuI4wY

Unlike DNA, RNA is single stranded and folds via bonds between pairs of complementary nucleotides while it is still being synthesized from DNA. One central problem in molecular biology is understanding the specific shape into which an RNA molecule folds, as its shape encodes functional information. We will focus on RNA secondary structure in this talk, that is the 2D arrangement of the final RNA configuration. For an RNA sequence, we will consider a representative set of secondary structures and discuss combinatorial methods to mine the structural information from the given ensemble. In particular, we will present a graph algorithms approach based on dissimilarity scores and community detection.

Lexicographic shellability is a powerful and popular technique used to study the topology of the order complex of a poset. The most useful flavor of lexicographic shellability is CL-shellability, which was introduced by Björner and Wachs in the early 1980s and which was then reformulated by them using the notion of recursive atom orderings. In this talk, I will start by providing a survey of some of the key ideas behind lexicographic shellability, particularly CL-shellability, recursive atom orderings, and CC-shellability, the more general version of lexicographic shellability introduced by Kozlov. Then, inspired by Bjorner and Wachs’ formulation of recursive atom orderings, I will introduce a recursive formulation of CC-shellability called generalized recursive atom orderings. I will then discuss some of the new and surprising results provided by this new formulation of CC-shellability.

Zoom recording

Using combinatorial structures to obtain resolutions of monomial ideals is an idea that traces back to Diana Taylor’s thesis, where a simplex associated to the generators of a monomial ideal was used to construct a free resolution of the ideal. This concept has been expanded over the years, with various authors determining conditions under which simplicial or cellular complexes can be associated to monomial ideals in ways that produce a free resolution.  

In a research project initiated at a BIRS workshop “Women in Commutative Algebra” in Fall 2019, the authors studied simplicial and cellular structures that produced resolutions of powers of monomialideals. This talk will focus on powers of square-free monomial ideals of projective dimension one. Faridi and Hersey proved that a monomial ideal has projective dimension one if and only if there is an associated tree (one dimensional acyclic simplicial complex) that supports a free resolution of the ideal. The talk will show how, for each power r >1, to use the tree associated to a square-free monomial ideal I of projective dimension one to produce a cellular complex that supports a free resolution of I^r. Moreover, each of these resolutions will be minimal resolutions. These cellular resolutions can also be viewed as strands of the resolution of the Rees algebra of I. This talk will contain joint work with Susan Cooper, Sabine El Khoury, Sara Faridi, Sarah Mayes-Tang, Liana Sega, and Sandra Spiroff.

Zoom recording

We present a novel code-based Authenticated Key Exchange (AKE) protocol.

Zoom recording available by request.

This talk will be about locally complete intersection maps of commutative noetherian rings. Results of Dwyer, Greenlees and Iyengar, and Pollitz lead to a characterization of the complete intersection property for a noetherian ring in terms of the structure, as a triangulated category, of the bounded derived category of the ring. In my talk I will present a similar characterization for locally complete intersection maps. This is joint work with Briggs, Iyengar, and Pollitz.

Zoom Recording