# ACGT Seminar

The Algebra, Combinatorics, Geometry, and Topology (ACGT) Seminar meets on Tuesdays at 12:45-2:00pm in Room 164 of the Adel Mathematics Building. If you are interested in giving a talk, please contact Dana C. Ernst, ACGT coordinator.

# Schedule Fall 2018

Note that talks are listed in reverse chronological order.

### The Complexities of Simplifying Addition: How DGHV Use Hamming Weights, Elementary Symmetric Polynomials, and “Three-For-Two”, to Make Their Encryption Scheme Fully Homomorphic

Date: 11/27/18

Speaker: Mark Haferkamp (NAU)

Abstract: Continuing from the previous talk, we first review van Dijk, Gentry, Halevi, and Vaikuntanathan’s (DGHV’s) somewhat homomorphic encryption scheme and outline how they convert it into a fully homomorphic encryption scheme. Then we work thru the details of why addition is so hard and how they do it. Finally, we tie up as many loose ends as time permits.

### Bounded Computations Over Encrypted Data: DGHV’s Somewhat Homomorphic Encryption Scheme Over the Integers, and Why It’s not Fully Homomorphic

Date: 11/20/18

Speaker: Mark Haferkamp (NAU)

Abstract: Want to have the convenience of having the cloud process your data but don’t want the privacy loss of the cloud knowing your data? Though inefficient, this is possible! We explore van Dijk, Gentry, Halevi, and Vaikuntanathan’s (DGHV’s) conceptually simple somewhat homomorphic encryption scheme which allows untrusted servers to compute certain functions over encrypted data. Then we look at why the scheme fails to handle certain functions and preview how DGHV extend their somewhat homomorphic encryption scheme into a fully homomorphic encryption scheme which can handle arbitrary binary computations.

### Braid shadows in simply-laced Coxeter systems

Date: 11/6/18, 11/13/18

Speaker: Dana Ernst (NAU)

Abstract: Every element $w$ of a Coxeter group $W$ can be written as an expression in the generators, and if the number of generators in an expression (including multiplicity) is minimal, we say that the expression is reduced. Every pair of reduced expressions for the same group element are related by a sequence of commutations and so-called braid moves. We say that two reduced expressions are braid equivalent if they are related by a sequence of braid moves. A Coxeter group is said to be simply-laced if every braid move is of the form $sts\mapsto tst$. Let $\overline{w} = s_{x_1}s_{x_2}\dots s_{x_n}$ be a reduced expression for $w$ in a simply-laced Coxeter group. Then the ordered triple $(i,i+1,i+2)$ is a called a braid shadow for $\overline{w}$ if and only if $s_{x_i}s_{x_{i+1}}s_{x_{i+2}}$ provides an opportunity to apply a braid move. If $(i,i+1,i+2)$ is a braid shadow for $\overline{w}$ such that $s_{x_i}s_{x_{i+1}}s_{x_{i+2}}=sts$, then we say that the support of $(i,i+1,i+2)$ relative to $\overline{w}$ is $\{s,t\}$. Suppose $\overline{w}_1$ and $\overline{w}_2$ are two braid equivalent reduced expressions for $w$ in a simply-laced Coxeter group $W$ such that $(i,i+1,i+2)$ is a braid shadow for both $\overline{w}_1$ and $\overline{w}_2$. We will prove that the supports of $(i,i+1,i+2)$ relative to both $\overline{w}_1$ and $\overline{w}_2$ are the equal as long as the Coxeter graph corresponding to $W$ does not have a three cycle.

### Half-cyclic codes and semi-divisors of $t^n-1$

Date: 10/23/18, 10/30/18

Speaker: Steve Wilson (NAU)

Abstract: Something old and something new: answering a question from last week and returning to the topic of last spring.

### Gaussian Fluctuations for Linear Eigenvalue Statistics of Products of Independent Random Matrices

Date: 10/18/18 (Special Thursday seminar, usual time and room)

Speaker: Natalie Coston

Abstract: After covering some background material and historical results, I fix an integer $m\geq 1$ and consider the product of $m$ independent $n\times n$ random matrices with independent and identically distributed (iid) entries. I then present results characterizing the limiting fluctuation of a linear statistic of the spectrum of the product as $n\rightarrow\infty$. I show the limiting variance of this test statistic is Gaussian and that the limiting variance is universal in the sense that it does not depend on m (the number of factor matrices) or on the distribution of the entries of the matrices. The main result generalizes and improves upon previous limit statements for the linear spectral statistics of a single iid matrix by Rider and Silverstein as well as Renfrew and O’Rourke.

### The Existence of Bandedly Nonsingular Matrices and the Connection to the Quasi-Cayleyness of the Praeger-Xu Graphs

Date: 10/9/18, 10/16/18

Speaker: Steve Wilson (NAU)

Abstract: I think that wins the competition for the most Jargon in a single talk title! First, for $k < n$, a band in a $k\times n$ matrix $M$ is one of the $k\times k$ submatrices, $n$ in number, formed by $k$ consecutive columns, including going around the corner. So, for example, if $M$ is $3\times 5$ with columns $x_1, x_2, x_3, x_4, x_5$, each of length 3, then the bands of $M$ are the matrices $[x_1 x_2 x_3], [x_2 x_3 x_4], [x_3 x_4 x_5], [x_4 x_5 x_1], [x_5 x_1 x_2]$. A matrix is bandedly nonsingular provided that each of its bands is nonsingular. We conjectured that for each $k < n$, there exists a $k\times n$ matrix which is bandedly non-singular. If the entries are from $\mathbb{R}$, this is trivial. (Homework 1: Prove that.) But I want this to be true when the entries are from a finite field, particularly $\mathbb{Z}_2$.

We will prove this theorem.

Why?

The why has to do with an important family of graphs, the Praeger-Xu graphs. In this talk, I will describe these graphs with pictures and definitions. In a series of papers with Primoz Potocnik and Robert Jajcay, we have investigated the question of which of the Praeger-Xu graphs qualifies as ‘Cayley’, and considered a related idea, that of a graph being ‘Quasi-Cayley’. We will say what both of these mean.

And then, finally!, we will show that the existence of a bandedly nonsingular $k\times n$ matrix over $\mathbb{Z}_2$ proves that $\it every$ Praeger-Xu graph is Quasi-Cayley.

### Cyclic and Constacyclic self-dual codes over $R_k$

Date: 9/25/18, 10/2/18

Speaker: Bahattin Yildiz (NAU)

Abstract: In this work, we consider constacyclic and cyclic self-dual codes over the rings $R_k$. We start with theoretical existence results for constacyclic and cyclic self-dual codes of any length over $R_k$ and then construct cyclic self-dual codes over $R_1 = F_2 + uF_2$ of even lengths from lifts of binary cyclic self-dual codes. We classify all free cyclic self-dual codes over $R_1$ of even lengths for which non-trivial such codes exist. In particular we demonstrate that our constructions provide a counter example to a claim made by Batoul et al. in 2014 and we explain why their claim fails.

### Exploring signed permutations of maximal reversal length

Date: 9/4/18, 9/11/18

Speaker: Tanner Rosenberg (NAU)

Abstract: One can model a configuration of genes as a permutation of the numbers 1 through $n$, where each number can be right-side-up or upside-down. In this model, one type of mutation corresponds to performing a 180-degree reversal. The reversal distance between two configurations of genes is the minimum number of reversals needed to convert the permutation corresponding to one gene configuration to the other. Although there are other types of mutations, we focus on reversals since they are the most common mutation and reversal distance provides a good estimate for genetic distance. While the maximal reversal distance among all permutations of 1 through $n$ and the identity permutation is known, in this presentation we discuss our progress toward describing the structure of permutations that attain the maximal reversal distance.