University of South Florida

College of Arts and Sciences

Search

Menu

Give Now

Title: Recovering Generators of Principal Ideals Using Subfield Structure and Applications to Cryptography Speaker: William Youmans Time: 4:00pm–5:00pm Place: NES 103

The principal ideal problem (PIP) is the problem of determining if a given ideal of a number field is principal, and if so, of finding a generator. Algorithms for resolving the PIP can be efficiently adapted to solve many hard problems in algebraic number theory, such as the computation of the class group, unit group, or \(S\)-unit group of a number field. The PIP is also connected to the search for approximate short vectors, known as the \(\gamma\)-Shortest Vector Problem (\(\gamma\)-SVP), in certain structured lattices called ideal lattices, which are prevalent in cryptography. We present an algorithm for resolving the PIP that leverages the norm relation techniques of Biasse, Fieker, Hofmann, and Page to efficiently reduce the PIP in a non-cyclic number field to instances of the PIP in subfields. Our algorithm is focused on practical performance and we demonstrate its viability by resolving instances of the PIP in cyclotomic fields of degree up to 1800. We further adapt this technique to the problem of finding mildly short vectors, solutions to \(\gamma\)-SVP for \(\gamma=2^{\tilde{O}(\sqrt{n})}\), in an ideal lattice of a cyclotomic field. Cramer, Ducas, and Wesolowski show that the search for mildly short vectors in such a lattice reduces efficiently to the PIP on a quantum computer. We describe a classical variant of this reduction that applies to non-cyclic cyclotomic fields. We show that there are infinite families of cyclotomic fields where this approach achieves a superpolynomial improvement over the state of the art.

Title: Hierarchical Locally Recoverable Codes: improved bound and new optimal codes Speaker: Vincenzo Pallozzi Lavorante Time: 4:00pm–5:00pm Place: NES 103

Hierarchical Locally Recoverable Codes allow to recover certain patterns of erasures by gradually looking at more components depending on the number of erasures that occurred. One can then design codes that recover one erasure by looking at \(b\) other components; \(\lambda\) erasures by looking at \(a\) other components; and \(d-1\) erasures by looking at \(k\) other components, where \(k\) is the dimension of the code. This is impactful from a practical perspective, as one can deal with the most likely scenario (one erasure) in the optimal way, with the less likely scenario (\(\lambda\) erasures) in an acceptable way, and still be able to recover \(d-1\) erasures by accessing a larger number of nodes.

The first part of this talk will serve as an introduction to locally recoverable codes, hierarchy and optimal bounds, while in the second part we will present our new construction together with some practical examples.

This is a joint work with A. Dukes and G. Micheli.

Title: Dynamical Irreducibility of Pure Polynomials over the Rational Field Speaker: Mohamed Darwish Time: 4:20pm–5:00pm Place: NES 103

A polynomial with rational coefficients is said to be pure with respect to a rational prime \(p\) if its Newton polygon has one slope. In this talk, we prove that the number of irreducible factors of the \(n\)-th iterate of a pure polynomial over the rational field \(Q\) is bounded independent of \(n\). In other words, we show that pure polynomials are eventually stable. Consequently, several eventual stability results available in literature follow; including the eventual stability of the polynomial \(x^d+c\in\mathbb{Q}[x]\), where \(c\ne 0,1\), is not a reciprocal of an integer. In addition, we establish the dynamical irreducibility, i.e., the irreducibility of all iterates, of a subfamily of pure polynomials, namely Dumas polynomials with respect to a rational prime \(p\) under a mild condition on the degree. This provides iterative techniques to produce irreducible polynomials in \(\mathbb{Q}[x]\) by composing pure polynomials of different degrees. In addition, we characterize all polynomials whose degrees are large enough that are not pure, yet they possess pure iterates. This implies the existence of polynomials in \(\mathbb{Z}[x]\) whose shifts are all dynamically irreducible. This is a joint work with Mohammad Sadek.

Title: Spin-network evaluations and pattern recognition Speaker: Emanuele Zappala Time: 4:00pm–5:00pm Place: NES 103

Spin-networks are graphs with edges colored by irreducible representations of a compact Lie group and vertices labeled by intertwiners. They play a fundamental role in quantum topology (Turaev-Viro invariants of \(3\)-manifolds), as well as in quantum gravity (Ponzano-Regge model). They have more recently found application in quantum machine learning. The systematic evaluation of spin-networks, however, is still computationally demanding, and it is very difficult in practice to perform computations due to the factorial nature of the computational complexity. In this talk, I will present an efficient approach (statistically sub-exponential) for the evaluation of spin-networks, and I will show how this procedure has applications in pattern recognition even without the need of training a neural network. This talk is based on ongoing work with Matteo Lulli (STUSTech) and Antonino Marciano (Fudan University and National Institute of Nuclear Physics, Italy), and fits in a larger quantum machine learning program with several additional co-authors: Farbocini (Tongji), Fields (Tufts), Greco (Trieste) and Gresnigt (Liverpool-Xi'an Jiatong).

Title: Normal Polynomials Over Finite Fields Speaker: Xiang-dong Hou Time: 4:00pm–5:00pm Place: NES 103

An irreducible polynomial over \(\mathbb{F}_q\) is said to be normal over \(\mathbb{F}_q\) if its roots are linearly independent over \(\mathbb{F}_q\). We show that there is a polynomial \[h_n\left(X_1,\dotsc,X_n\right) \in \mathbb{Z}\left[X_1,\dotsc,X_n\right],\] independent of \(q\), such that if an irreducible polynomial \[f=X^n+a_1X^{n-1}+\dotsb+a_n\in\mathbb{F}_q[X]\] is such that \(h_n\left(a_1,\dotsc,a_n\right)\ne 0\), then \(f\) is normal over \(\mathbb{F}_q\). The polynomial \(h_n\left(X_1,\dotsc,X_n\right)\) is computed explicitly for \(n\le 5\) and partially for \(n=6\). When \(\operatorname{char}\,\mathbb{F}_q=p\), we also show that there is a polynomial \(h_{p,n}\left(X_1,\dotsc,X_n\right)\in\mathbb{F}_p\left[X_1,\dotsc,X_n\right]\), depending on \(p\), which is simpler than \(h_n\) but has the same property. These results remain valid for monic separable irreducible polynomials over an arbitrary field with a cyclic Galois group.