Anina Gruica (Eindhoven University of Technology)

The Density of Maximum-Rank-Distance Codes

This talk focuses on rank-metric codes, which are linear spaces of matrices over a finite field F_q in which every nonzero matrix has rank at least d (the minimum distance of the code). Originally introduced by Delsarte for combinatorial interest, in the last few decades rank-metric codes have been extensively studied in connection with applications in information theory and several areas of pure and applied mathematics. 

A central open problem in coding theory is to count the number of rank-metric codes having maximum dimension for a certain minimum distance. These codes are called maximum-rank-distance (MRD) codes. In this talk, I will address this problem from an asymptotic viewpoint, focusing on the density of MRD codes as the field size q tends to infinity. 

This instance of the problem has been studied using various different approaches, but none of the techniques proposed so far was enough to determine whether MRD codes are sparse or dense (or neither) as the field size grows. I will explain how this problem can be solved using a combinatorial approach based on the parameters of certain bipartite graphs, proving in particular that MRD codes are (very) sparse for large q.g

Leonardo Garcia-Heveling (Radboud University)

From spacetime to metric spaces

General relativity describes gravity through the geometry of spacetime. A big open problem is how to compare different spacetimes. For example: in which sense is a vacuum spacetime close to a spacetime containing only a small amount of mass?

At the heart of this problem lies the fact that spacetimes are manifolds equipped with a metric tensor of Lorentzian signature (-+++). The minus sign is there to single out one direction as the time direction. Such a Lorentzian metric is not positive definite, and therefore we cannot apply the usual notions of closeness between metric spaces, like the
Gromov-Hausdorff distance. Sormani-Vega (2016) proposed to address this by equipping each spacetime with its so-called null distance, which is positive definite. For this approach to succeed, the null distance has to encode the physically relevant information about the spacetime.

In this talk, I will explain how indeed an important physical condition on the spacetime, global hyperbolicity, is encoded in its null distance. Global hyperbolicity is the condition that guarantees well-posedness for the Einstein equations of general relativity. I will show that it is equivalent to completeness of the null distance, the usual requirement that every Cauchy sequence has a limit.

Luis Felipe Vargas (CWI)

Sums of squares, copositive matrices and the stability number of a graph.

The connection between nonnegative polynomials and sums of squares has been much studied in the last two centuries. In 1888, Hilbert proved that there exist nonnegative polynomials that cannot be written as a sum of squares of other polynomials. Other types of certificates for nonnegativity involving sums of squares of polynomials have been studied. In 1995, Reznick showed that, for any positive definite form f, there exists an integer r for which (\sum_{i=1}^nx_i^2)^rf  is a sum of squares of polynomials. In general, the `positive definite’ condition is necessary.

In this lecture, we study the existence of these Reznick-type positivity certificates for nonnegative forms (possibly with zeros) in the context of copositive matrices and their applications to the Stable Set Problem. A matrix is copositive if an associated quartic form is positive semidefinite. Thus, we study copositive matrices for which the associated quartic form admits a Reznick-type certificate. As main results, we characterize the matrix sizes for which this certificate always exists, and we show that this certificate exists for a broad class of copositive matrices arising from graphs. This last result implies the finite convergence of a semidefinite hierarchy for approximating the stability number of a graph.

Perfect Y. Gidisu (Eindhoven University of Technology)

Generalized CUR-type factorizations for large-scale matrices

A CUR factorization is a type of low-rank matrix decomposition that approximates a given matrix using a small subset of its rows and columns as bases for its row and column spaces. Unlike traditional low-rank decompositions, which use orthonormal bases, a CUR factorization offers advantages such as preserving sparsity and non-negativity, improved data interpretation, and reduced storage requirements.

Mathematically, we aim to solve a combinatorial problem where we select a subset of rows and columns from a data matrix to construct thin matrices C and R.  The goal is to minimize the approximation error over all possible choices for C and R. An exact solution to this problem is intractable, so researchers seek efficient mathematical methods that yield a solution not worse than the optimal by some factor. However, finding deterministic algorithms that result in a modest factor is still an open problem. We have developed efficient algorithms that seek to minimize this factor while also extending the CUR factorization to multiple matrices.