November 14, 2018: Yan Zhuang

Shuffle-Compatible Permutation Statistics

Yan Zhuang — Davidson College

It has been observed since the early work of Richard Stanley that several well-known permutation statistics are “compatible” with the operation of shuffling permutations. In joint work with Ira Gessel, we formalize this notion of a shuffle-compatible permutation statistic and develop a unifying framework for studying shuffle-compatibility, which has close connections to the theory of P-partitions, quasisymmetric functions, and noncommutative symmetric functions. In this talk, I will survey the main results of our work as well as several new directions of research concerning shuffle-compatibility.

November 8, 2018: Michael Cowen and James Gossell

The power edge ideal of a finite simple graph

Michael Cowen and James Gossell — Clemson University

Every electric power system can be modeled by a graph G whose vertices represent electrical buses and whose edges represent power lines. A phasor measurement unit (PMU) is a monitor that can be placed at a bus to observe the voltage at that bus as well as the current and its phase through all incident power lines. The problem of monitoring the entire electric power system using the fewest number of PMUs is closely related to vertex covering and dominating set problems in graph theory.

In this talk, we will give an overview of the PMU placement problem and its connections to commutative ring theory. By defining the power edge ideal IPG of a graph G, we will show how to use graphs of electric power grids to generate polynomial rings with desired algebraic properties. In particular, we will classify the trees G for which IPG is Cohen-Macaulay and prove that every such ideal is also a complete intersection.

This project is joint work with Alan Hahn, Frank Moore, and Sean Sather-Wagstaff.

October 25, 2018: Robert Hildebrand

Mixed Integer Polynomial Optimization  – Algorithms and Complexity for Linear and Non-Linear Cases when the Dimension is Fixed

(Joint AMD and OR Seminar)

Robert Hildebrand — Virginia Tech

Integer Programming (or Integer Optimization) is the problem if optimizing an objective function over a set of feasible points that have the restriction that some variables must take integer values.  Integer linear programming (optimizing a linear function over linear constraints and integer constraints) is NP-Hard, while the continuous counterpart, Linear Programming, is polynomial time solvable.  Since the linear case is NP-Hard, the non-linear case of integer programming is also NP-Hard.  The story becomes much different when the dimension is considered a fixed number.  For instance, what is the complexity of integer linear programming when there are only 3 variables?   Lenstra proved in the 80’s that in fact, for any fixed dimension, integer linear programming can be solved in polynomial time.  This result hinges on the lattice basis reduction algorithms such as the famous LLL algorithm.    Surprisingly, the question of complexity in fixed dimension is very unclear even for quadratic integer programming.  We will survey Lenstra-type algorithms for integer programming and show recent results on convex and non-convex mixed integer programming.

October 18, 2018: Yen Duong

Random groups and cubulations

Yen Duong — Invited AWM speaker

Special cube complexes have been a hot topic for a few years now for their versatility and usefulness. Following a construction of Sageev we can cubulate all sorts of groups, and specifically I’ll explain Gromov’s density model of random groups, the square model of random groups, and examples of Sageev’s cubulation with random groups, and why we would want to do all this.

 

October 11, 2018: Jim Coykendall

Factorization and the Half-Factorial Property

Jim Coykendall — Clemson University

The notion of unique factorization is central in commutative algebra and number theory (with very important ramifications spilling over into almost every branch of mathematics). In general, “factorization” may be considered the study of the multiplicative decomposition(s) of elements in a ring (usually an integral domain for our purposes), and generalizations of unique factorization are of much interest.

One of the most infamous generalizations of unique factorization is the half-factorial property. Loosely speaking, a half-factorial domain is an integral domain in which elements may not factor uniquely, but any two decompositions of the same nonzero element into irreducibles will have the same number of irreducibles involved (counting possible multiplicities). The aim of this talk will be to give an overview of this generalization of unique factorization from its inception through some very recent results. Along the way, the talk will be seasoned and flavored with many examples comparing and contrasting the half-factorial property with the more familiar notion of unique factorization. Graduate students are especially encouraged to have their lives changed by this talk!

September 20, 2018: Shuhong Gao

Efficient Fully Homomorphic Encryption Schemes

Shuhong Gao — Clemson University

As cloud computing, internet of things (IoT) and blockchain technology become  increasingly  prevalent, there is an urgent need to protect the privacy of massive volumes of  sensitive data collected or stored in distributed  computer networks  or cloud  servers,  as many of the networks or servers can be vulnerable to external and internal threats such as malicious hackers or curious insiders.   The Holy-Grail of cryptography is to have practical fully homomorphic encryption (FHE) schemes that allow any third party (including cloud servers, hackers, miners or  insiders) to perform searching or analytics of an arbitrary function on encrypted data without decryption, while no information on the original data is ever leaked. The breakthrough was made by Gentry in 2009  who discovered the first FHE scheme, and since then  many improvements have been made on designing more efficient homomorphic encryption schemes.  The main bottlenecks are in bootstrapping and large cipher expansion factor (the size ratio of ciphertexts over messages): the current best FHE schemes compute bootstrapping of one bit operation in 0.013 second and still have a cipher expansion factor of 10,000. In this talk, we present a compact  FHE scheme whose  bootstrapping speed is slightly slower but  whose cipher expansion factor  is  only 6  under private-key  encryption  and 20  under public-key encryption,  hence practical in term of storage.

September 13, 2018: Cynthia Ramiharimanana

Minimal Ramification Problem

Cynthia Ramiharimanana — Clemson University

Minimal ramification problem can be considered as a quantitative version of Inverse Galois Problem. The latter is a question that asks whether every finite group is a Galois group of a Galois extension of the field of rational numbers Q. It is one of the important problems in Field Arithmetic and Algebraic Number Theory. For a given finite group G, let Ram(G) be the minimal integer for which there exists a Galois extension of N/Q that ramifies exactly at Ram(G) primes. The task in minimal ramification problem is to compute or to bound Ram(G). In this talk, I will give an overview of the problem and some results, and then we will talk about current and future research.

April 19: Benjamin Case

Lattice Cryptography and Attacks

Benjamin Case – Clemson University

In this seminar we will overview lattice cryptography and its usefulness for post-quantum security and fully homomorphic encryption. In particular, we will look at the security of schemes based on the Learning with Errors (LWE) problem. Discrete probability distributions defined over rings and finite fields play an important role in the security of lattice-based schemes; and through studying how linear combinations of these distributions behave, we will reveal some weak instances of the LWE problem that are not suitable for building encryption schemes.

March 15, 2018: Csaba Biro

Coloring geometric intersection graphs

Csaba Biro – University of Louisville

Many classical hard algorithmic problems on graphs, like coloring, clique number, or the Hamiltonian cycle problem can be sped up for planar graphs resulting in algorithms of time complexity $2^{O(\sqrt{n})}$. We study the coloring problem of unit disk intersection graphs, where the number of colors is part of the input. We conclude that, assuming the Exponential Time Hypothesis, no such speedup is possible. In fact we prove a series of lower bounds depending on further restrictions on the number of colors. Generalizations for other shapes and higher dimensions were also achieved. Joint work with E. Bonnet, D. Marx, T. Miltzow, and P. Rzazewski.

Refreshments at 3:00, Martin-O, first floor.

March 6, 2018: Luigi Ferraro

Hopf Algebra Action on some AS-Regular Algebras of Small Dimension

Luigi Ferraro – Wake Forest University

The classical Chevalley-Shephard-Todd Theorem gives a characterization of when a group acting linearly on the commutative polynomial ring has a ring of invariants that is isomorphic to a polynomial ring. Understanding when group actions (or more generally, Hopf actions) on AS-regular algebras give AS-regular invariant rings has proven to be a difficult problem. We pro- vide some new examples of Hopf actions on some AS-regular algebras such that the ring of invariants is also AS-regular.

Refreshments at 3:00, Martin-O, first floor. (Note that this talk is on a Tuesday.)