(Fri, not too early) Aida Abiad Monge (U Maastricht) - A spectral approach to the distance matrix of a graph
Spectral graph theory deals with the relation between the structure of a graph and the eigenvalues (spectrum) of an associated matrix, such as the Laplacian matrix or the distance matrix. In this talk, we will discuss some spectral properties of the distance matrix of a graph. It was conjectured by Graham and Lovász that the coefficients of the distance characteristic polynomial of a tree on n vertices are unimodal and have their peak at [n/2]. We will also report on recent results concerning this conjecture.
(Thu) Elena Kirshanova (U Lyon) - Sieving algorithms for the Shortest Vector Problem
In this talk I give an overview on the complexity of the algorithms for the Shortest Vector Problem (SVP) with the focus on a particular family of algorithms: sieving algorithms. First, I explain why this problem is important and how the complexity of SVP algorithms impacts parameters for cryptographic protocols. Then, I present recent advances in memory efficient versions of sieving algorithms. I explain locality-sensitive techniques for these type of algorithms. The part of the talk is based on joint works with Gottfried Herold and Thijs Laarhoven. Finally, I present recent advances in practical aspects of sieving algorithm for SVP. I describe technical challenges that arise when one tries to make sieving algorithms practical, and how one can overcome some of them. This part of the talk is the on-going work with Martin R. Albrecht, Leo Ducas, Gottfried Herold, Eamonn W. Postlethwaite, Marc Stevens.
(Thu) Farbod Shokrieh (U Copenhagen) - Graphs and arithmetic geometry
Graphs can be viewed as analogues of Riemann surfaces. For example there is a notion of Jacobians for graphs, which is closely related to the classical matrix-tree theorem. More classically, graphs can be viewed as electrical networks. I will explain the interplay between these points of view, as well as some recent applications to problems in arithmetic geometry.
(Thu) Arne Smeets (RU Nijmegen) - Diophantine problems for orbifold pairs
The study of Diophantine problems, i.e. of rational and integral points on algebraic varieties, is a classical and rich subfield of number theory and arithmetic geometry. I will explain how Campana's framework of "orbifold pairs" - which has its origins in birational geometry over the complex numbers - yields many new interesting Diophantine problems, which one can interpret as a way to 'interpolate' between problems having to do with rational points on the one hand, and with integral points on the other hand. I will also report on some recent work by the author on such problems: firstly, a Mordell-type conjecture over function fields; secondly, a Batyrev-Manin-type conjecture (counting points of bounded height) over number fields.
(Fri) Renata Sotirov (Tilburg University) - The Quadratic Shortest Path Problem
The quadratic shortest path problem (QSPP) is the problem of finding a path in a directed graph such that the sum of interaction costs over all pairs of arcs on the path is minimized. This problem has recently been proven NP-hard. We first classify QSPP instances into linearizable and non-linearizable instances. The linearizable QSPP instances are instances whose optimal solution can be obtained by solving the corresponding (easy) instance of the shortest path problem. We present a polynomial-time algorithm that solves the linearization problem for the QSPP, i.e., verifies whether a given QSPP instance is linearizable. For a non-linearizable instance, our algorithm generates a system of equations that is further exploited to compute lower bounds of the original problem. To the best of our knowledge, this is the first study in which the linearization problem is exploited to compute bounds for the corresponding combinatorial optimization problem. In the last part of the talk, we present a semidefinite programming relaxation for the QSPP and show how to use the alternating direction method of multipliers (ADMM) to solve the relaxation. Our approach results in solving large scale instance of the QSPP to optimality. Joint work with Hao Hu, Tilburg University.
Arthur Bik (U Bern) - Polynomials of bounded strength
Storing a homogeneous polynomial in K[x_1, ... ,x_n] of degree d becomes difficult very fast as n -> oo. The number of values we need to remember is a polynomial of degree d in n. However, if we only consider polynomials that can be expressed as the sum of at most k products of polynomials of lower degree, then the number of values that we need is at most k times a polynomial of degree d-1. In this talk, I will discuss joint work with Jan Draisma and Rob Eggermont stating that for every functorial family of Zariski-closed subsets X_n of K[x_1, ... , x_n]_(d) either X_n = K[x_1, ... , x_n]_(d) for all n or every polynomial f in X_n can be written as the sum of k products where k is a constant that does not depend on n or f.
Francisco Fernandes Pereira (TU/e) - Entanglement-assisted quantum error correcting codes from algebraic geometry codes
The prospect of practical large-scale quantum computers and the use of quantum communication is only possible if quantum error correcting codes are implemented in them. They play the role of suppressing noise and decoherence by introducing redundancy. A few strategies can be used to improve the parameters of these codes. For example, entanglement can provide a way for quantum error correcting codes to achieve higher rates. Such codes are known as entanglement-assisted quantum error correcting codes (EAQECC). Another property of these codes is that they can attain the entanglement assisted quantum capacity of a depolarizing channel when the quantum code has maximal entanglement. In this talk we use algebraic geometry codes to construct EAQECCs that has maximal entanglement and are almost near maximal distance separable codes. We also show some examples of the possible parameters of the quantum codes that can be obtained from the presented method.
Sam van Gool (ILLC) - Pointlike sets for varieties determined by groups
I will present recent joint work with B. Steinberg in finite semigroup theory, which has applications in logic and regular language theory. Our main technical result is a characterization of the subsets of a finite semigroup that are pointlike with respect to a variety of the form H-bar. Here, H-bar denotes the variety of finite semigroups all of whose subgroups lie in a fixed variety of finite groups H. Our characterization is effective whenever H has decidable membership problem. Taking H to be the variety of solvable groups, our result gives an algorithm to decide whether two regular languages can be separated by a language definable in first order logic with modular counting quantifiers.
Sophie Huiberts (CWI) - A Friendly Smoothed Analysis of the Simplex Method
The simplex method for linear programming is known for its good performance in practice, although the theoretical worst-case performance is exponential in the input size. The smoothed complexity framework of Spielman and Teng (2001) aims to explain the good practical performance. In our work, we improve on all previous smoothed complexity results for the simplex algorithm on all parameter regimes with a substantially simpler and more general proof. This is joint work with Daniel Dadush.
Harry Smit (UU) - L-series and isogenies of abelian varieties
A theorem of Faltings states that two non-isogenous abelian varieties defined over a number field can be distinguished by the L-functions of their reductions. The global L-function does not have the same capacity, as one cannot distinguish between primes with the same characteristic. To work around this, we consider all L-functions twisted with Dirichlet characters and show that this characterises the isogeny type of an abelian variety.
Roland Vincze (U Maastricht) - A time- and space-optimal algorithm for the many-visits TSP
The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour that visits each city a prescribed number of times. Travel costs may be asymmetric and visiting a city twice in a row may incur a non-zero cost. The fastest known exact algorithm is due to Cosmadakis and Papadimitriou (SICOMP, 1984) and has time and space complexity superexponential in the number of cities. We propose an exact algorithm that runs in single-exponential time and requires only polynomial space, which is, assuming the ETH, asymptotically optimal.
Wouter Zomervrucht (UL) - TBA