New PhD Student

Freja Elbro, PhD student

New PhD Student

Johan S. R. Nielsen No Comments

Freja Elbro started a few months ago as a PhD student with Lars R. Knudsen in the Cyber Security section but is from 1st May co-advised by Johan Rosenkilde of the Algebra group.

Freja’s project is quantum-safe asymmetric cryptography based on coding theory, with a focus on McEliece-like constructions.

Sven Puchinger, Postdoc

Postdoc Sven Puchinger started

Johan S. R. Nielsen No Comments

The Algebra group has a great new addition: Postdoc Sven Puchinger started 1st October on his 2-year H. C. Ørsted fellowship. Sven Puchinger has his PhD Degree from the University of Ulm under the supervision of Martin Bossert (where Johan was also a postdoc in 2014-2015), and he spent the last 1,5 years as a postdoc at Technical University of Munich.

His research interests are broadly within algebraic coding theory, from new code constructions to decoding and fancy applications. Sven already has numerous joint papers with Johan and Peter, and we foresee that his postdoc here will be very fruitful.

Coding Theory Cartoon

Johan S. R. Nielsen No Comments

Grigory and Leonardo created this great cartoon explaining the principles and importance of coding theory – illustrated by a cross-galactic love story!

The video was made as their contribution to the DTU Compute PhD Bazaar.

Enjoy:

SIAM/AG 2019

Johan S. R. Nielsen No Comments

Johan and Grigory participated in the conference SIAM Applied Algebraic Geometry 2019. The conference had many talks on computer algebra, coding theory and cryptography. Johan gave a talk entitled “Decoding of Gabidulin codes and friends using row reduction of skew polynomial matrices”.

Research visit by Sven Puchinger

Johan S. R. Nielsen No Comments

The Algebra group was visited late January 2019 by Sven Puchinger who is a postdoc at TU München. Sven has visited us before, and is also a former colleague of Johan at Ulm University in 2013-2014. Sven has numerous research papers jointly written with Johan and Peter.

During the visit, we mostly discussed Twisted Reed-Solomon codes: these are optimal codes (MDS) which are constructed by slightly “twisting” a Reed-Solomon code by carefully adding a monomial to the evaluation polynomials. We proposed the codes in an ISIT paper in 2017, and in 2018 we derived more properties and proposed them for quantum-computer-resilient cryptography. After Sven’s visit, we now have new observations which we will write down in an upcoming paper.

Sven also gave a very nice talk entitled “On Decoding and Applications of Interleaved Gabidulin Codes”.

Leonardo Landi, PhD at Algebra Group at DTU

New PhD Student: Leonardo Landi

Johan S. R. Nielsen No Comments

Our new PhD student Leonardo Landi started 1st January 2019! Leonardo holds a Master’s degree from the University of Parma, Italy. His PhD project has the tentative title “Curves and Error-Correction”: the aim is to get a better insight in the structure of algebraic geometry codes constructed using towers of function fields.

Research project in the media

Johan S. R. Nielsen No Comments

Our research project “Correcting on a Curve”, funded by DFF-FNU, has received attention in the media, more specifically the web-based business newspaper Finans.dk:

Danske forskere vil udvikle verdens hurtigste fejlrettende koder

(The full article is unfortunately behind a paywall)

Our project is also featured by DFF’s web page for funded projects:

https://dff.dk/cases/forskere-skal-udvikle-verdens-hurtigste-fejlrettende-koder-til-digital-kommunikation

Paper on record-breaking decoding accepted

Johan S. R. Nielsen No Comments

The paper “Improved Power Decoding of Interleaved One-Point Hermitian Codes” was accepted for publication in the journal Designs, Codes and Cryptography, and should appear soon!

Visit by Prof. Mark Giesbrecht

Johan S. R. Nielsen No Comments

During the first week of September 2018, Professor Mark Giesbrecht visited Johan. Mark is Director of the David R. Cheriton School of Computer Science at the University of Waterloo. His research is in symbolic mathematical computation, both developing the algorithmic and complexity theoretical tools as well as building computer algebra software. He was named ACM Distinguished Scientist in 2013 and received an NSERC Synergy Award in 2003 for work with MapleSoft on Maple.

During his visit, Mark and Johan worked together on computing reduced forms of matrices over Ore polynomial rings, with a focus on \(\mathbb Q[x][\partial; d/dx]\). Ore polynomials are a type of non-commutative polynomials which has applications in such diverse fields as partial differential equations, control theory, and coding theory. Matrices over such polynomials arise e.g. when studying systems of equations in these applications, and reducing the matrices can be used to find small representations of the systems which can reduce later, computationally hard steps. The work is together with Arne Storjohann also at University of Waterloo with whom Johan has worked on this issue earlier.

During his visit, Mark also gave a talk entitled “Algorithms and statistics for additive polynomials”

Abstract:

The additive or linearized polynomials were introduced by Ore in 1933 as an analogy over finite fields to his theory of difference and difference equations over function fields. The additive polynomials over a finite field \(\mathbb{F}_q\), where \(q=p^e\) for some prime \(p\),
are those of the form

$$f = f_0 x + f_1 x^p + f_2 x^{p^2} + … + f_m x^{p^m} \in \mathbb{F}_q[x]$$

They form a non-commutative left-euclidean principal ideal domain under the usual addition and functional composition, and possess a rich structure in both their decomposition structures and root geometries. Additive polynomials have been employed in number theory and algebraic geometry, and applied to constructing error-correcting codes and cryptographic protocols. In this talk we will present fast algorithms for decomposing and factoring additive polynomials, and also for counting the number of decompositions with particular degree sequences.

Algebraically, we show how to reduce the problem of decomposing additive polynomials to decomposing a related associative algebra, the eigenring. We give computationally efficient versions of the Jordan-Holder and Krull-Schmidt theorems in this context to describe all possible factorization. Geometrically, we show how to compute a representation of the Frobenius operator on the space of roots, and how its Jordan form can be used to count the number of decompositions. We also describe an inverse theory, from which we can construct and count the number of additive polynomials with specified factorization patterns.

Some of this is joint work with Joachim von zur Gathen (Bonn) and Konstantin Ziegler (Landshut).

Paper on computing reduced form of polynomial matrices presented

Johan S. R. Nielsen No Comments

The paper “Computing Popov and Hermite forms of rectangular polynomial matrices” was accepted at the prestigious ISSAC conference  earlier this year, and was recently presented at the conference in New York.

The paper is a collaboration between Johan Rosenkilde from the group,  former postdoc Vincent Neiger,  and former Master’s thesis student Grigory Solomatov. Parts of the results were obtained by Grigory during his Master’s thesis!

The paper concerns the computation of something similar to Gaussian elimination but for matrices with entries which are polynomials (univariate).  These kind of computations were recently improved by Vincent for square matrices, but it was still open how to generalise these results to cover rectangular matrices. There are good reasons why this generalisation is not completely straightforward, and in fact most of Grigory’s thesis work was about shooting down all the obvious ways one could think of doing this.

In the end, we found a very elegant randomized algorithm, which is fast in many cases, and a more sophisticated algorithm which works well in almost all cases. The issue is not completely settled, though, and there are still a spectrum of input for which we believe a slightly faster algorithm should exist. That’s for future work!

The full paper can be found here.