Invited speakers:

Sander Dahmen (VU Amsterdam): Congruent number curves and Lucas sequences

A standard technique for determining the perfect powers in a Lucas sequence combines bounds coming from linear forms in logarithms with local information obtained via Frey curves and modularity. The key to this approach is the fact that such a Diophantine problem can be translated into a ternary Diophantine equation over the rationals for which Frey curves are available. In this talk we consider shifted powers ($ax^n+b$) in Lucas sequences, which do not typically correspond to ternary equations over the rationals. However, they do, under certain hypotheses, lead to ternary equations over totally real fields, allowing us to employ Frey curves over those fields. We illustrate this approach by solving a specific case of such a shifted powers problem, which yields the final ingredient required in work of Bennett on integral points on congruent number curves. This is joint work with Michael Bennett, Maurice Mignotte, and Samir Siksek.

Nadia Heninger (UPenn):

Leo van Iersel (TU Delft): Reconstructing evolutionary histories

A phylogenetic network is a directed graph that describes the evolutionary history of a set of objects. Such networks are especially relevant in biology, where the objects are different species, and in linguistics, where the objects are different
languages. Reconstructing phylogenetic networks is significantly more challenging than the well-studied problem of reconstructing phylogenetic trees. I will discuss different approaches that have been proposed quite recently, including reconstructing a network from a collection of trees, from sequences and from smaller networks.

Max Klimm (TU Berlin): The equilibrium existence problem for weighted congestion games

Weighted congestion games are a class of noncooperative games that constitute an elegant model for the resource usage by selfish players. In a weighted congestion game, we are given a finite set of resources and a strategy of each player is to choose a subset of them. The private cost of each player is the sum of the costs of the chosen resources which depends on the total weight of the players using them. It is known that weighted congestion games need not possess a pure Nash equilibrium, i.e. a strategy vector from which no player can profitably deviate. We give a complete characterization of the maximal set of cost functions that one can allow on the resources in order to guarantee the existence of a pure Nash equilibrium. Further results on the existence of pure Nash equilibria in related models are given.

Matthias Mnich (U Bonn): Combinatorial optimization above and below guaranteed values

Many fundamental combinatorial optimization problems exhibit the property that the value of an optimal solution grows asymptotically with the length of the input. As one is generally interested in algorithmically solving large instances, algorithms solving these instances always produce output of which a large part of which simply repeats the input. This is not very efficient, in particular if the problem to solve is NP-hard. To circumvent this, we seek algorithms solving NP-hard optimization problems in time that confines the expected combinatorial explosion to the small gain of the optimal objective over the lower bound generated from the instance size. We give a survey on this area, with many positive algorithmic and negative hardness results for fundamental problems like Max Sat, Max Cut, Max Independent Set, Min Vertex Cover, and Constraint Satisfaction.

Noriko Yui (Queen's University, MPIM Bonn): Update on automorphy of Calabi-Yau varieties over Q

Let X be a Calabi-Yau variety of dimension d. We will focus on the cases where d ≤ 3. Calabi–Yau varieties of dimension 1, 2 are elliptic curves and K3 surfaces, respectively. The dimension 3 Calabi–Yau varieties are Calabi–Yau threefolds where one can observe, among other things, mirror symmetry in full force. I will consider Calabi–Yau varieties defined over Q. Our goal is to discuss the modularity/automorphy of the (l-adic) Galois representations associated to the d-th etale cohomology groups of these Calabi–Yau varieties. In the last two decades, the modularity has been established for Calabi–Yau varieties over Q, whose Galois representations are two-dimensional. In this talk, I will discuss the automorphy/modularity of higher dimensional Galois representations (e.g., of dimension > 2). I will present some examples in support of the modularity/automorphy focusing on the two (or three) situations: (1) when X is equipped with a large automorphism group, and the Galois representation of X splits into smaller dimensional pieces, (2) when X is of CM type, and (3) the intersection of (1) and (2).

Contributed speakers:

Sabine Burgdorf (CWI) - Polyhedral approximation of the completely positive semidefinite cone

The completely positive semidefinite cone $\mathcal{CS}_+^n$ is a generalization of the completely positive cone: it consists of all the nxn symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size instead of Gram representations by nonnegative vectors. This cone is used by Laurent and Piovesan to model quantum graph parameters as conic optimization problems, and by Mancinska and Roberson to characterize the set of bipartite quantum correlations as projection of an affine section of it. We will present a hierarchy of polyhedral cones which covers the interior of $\mathcal{CS}_+^n$ . This hierarchy will then be used for computing some variant of the quantum chromatic number by way of a linear program. Joint work with M. Laurent and T. Piovesan.

Abtien Javanpeykar (UL) - TBA

Thijs Laarhoven - Sieving for shortest lattice vectors using locality-sensitive hashing

Most lattice-based cryptographic primitives rely on the shortest vector problem (SVP) on lattices being hard. To assess the computational hardness of SVP and breaking these schemes, one commonly relies on the estimated time complexity of enumeration for solving SVP. In 2001 the breakthrough work of Ajtai et al. showed that SVP can actually be solved faster in high dimensions, using a technique called sieving. Although this technique seemed impractical at first, various improvements have since shown that sieving may be competitive with enumeration after all. In this talk we will look at recent advances in sieving using a technique from nearest-neighbor searching called locality-sensitive hashing.

Sietse Ringers (RUG) -

Zhao Sun (TiU) - Convergence analysis for Lasserre's measure-based hierarchy of upper
bounds for polynomial optimization

We consider the problem of minimizing a polynomial over a compact set, and analyze a measure-based hierarchy of upper bounds proposed by Lasserre. This hierarchy is obtained by searching for an optimal probability density function which is a sum of squares of polynomials, so that the expectation is minimized. In this talk, we will show its rate of convergence. The main idea is to use the truncated Taylor series of the Gaussian distribution function.

Shin-ichi Tanigawa (CWI) - Matroids of group-labeled graphs in graph rigidity

A group-labeled graph is a graph whose oriented edges are labeled invertibly from a group. Two classes of matroids on group-labeled graphs, called frame matroids (Dowling geometries) and lift matroids, have been extensively studied. In this talk I will show extensions of these matroids in two ways. The first one is extending the rank function of each matroid based on submodular functions over the underlying groups, and another one is extending the canonical linear representation of the union of copies of a frame matroid or a lift matroid. It turns out that linear matroids of the latter extension are special cases of the first extensions. This work is motivated from recent research on the rigidity of graphs (bar-joint frameworks) with symmetries. I will show various examples of new matroids appeared in the analysis of the infinitesimal  rigidity of graphs (frameworks) with a point group or a crystallographic symmetry.

Christine van Vreedendaal (TUE) - Tighter, faster, simpler side-channel security evaluations beyond computing power

A Eurocrypt 2013 paper “Security evaluations beyond computing power: How to analyze side-channel attacks you cannot mount?” by Veyrat-Charvillon, G´erard, and Standaert proposed a “Rank Estimation Algorithm” (REA) to estimate the difficulty of finding a secret key given side-channel information from independent subkeys, such as the 16 key bytes in AES-128 or the 32 key bytes in AES-256. The lower and upper bounds produced by the algorithm are far apart for most key ranks. The algorithm can produce tighter bounds but then becomes exponentially slower; it also becomes exponentially slower as the number of subkeys increases. We introduce two better algorithms for the same problem. The first, the “Extended Rank Estimation Algorithm” (EREA), is an extension of REA using statistical sampling as a second step to increase the speed of tightening the bounds on the rank. The second, the “Polynomial Rank Outlining Algorithm” (PRO), is a new approach to computing the rank. PRO can handle a much larger number of subkeys efficiently, is easy to implement in a computer-algebra system such as Sage, and produces much tighter bounds than REA in less time.

Chitchanok Chuengsatiansup - Curve41417: Karatsuba revisited

The Karatsuba's algorithm is a multiplication algorithm that is faster than a schoolbook multiplication.  The speedup comes from trading multiplications into additions/subtractions. However, the size of integers being performed multiplication must be large enough to benefit from this trade-off.  It has been believed that the size of integers to be useful is beyond th size of integers used in elliptic curve cryptography (ECC). In this talk, I will focus on a prime field of size 2^{414}-17 which is used in ECC.  I will explain how Karatsuba's algorithm can be combined with other techniques to speed up a scalar multiplication, i.e., computing nP for a scalar n and a point P, which is a very time-consuming operation in many ECC protocol.

Mathematics cluster DIAMANT

Upcoming events

NMC 2020 and Diamant symposium
14-4-2020 - 16-4-2020

News - more news

Call for PhD project proposals

NWO has issued a cluster-wide call for PhD project proposals. Researchers can apply if they are employed (i.e., hold a salaried position) at a Dutch university or a research institute recognised by NWO, and also have an appointment period for at least the duration of the application procedure and the entire duration of the research for which the grant is being applied for.

Read more.

ERC Starting Grant for Jesper Nederlof

Jesper Nederlof (TU/e) has been awarded an ERC Starting Grant of almost 1.5 ME. Nederlof will design faster algorithms for hard computational problems in computer science. The grant provides the researcher with the opportunity to further elaborate his own ideas during a period of five years.

Read more.

Full professor position in Discrete Mathematics in Delft

Delft Institute of Applied mathematics, Delft University of Technology, seeks a full Professor in the field of Discrete Mathematics. A description of the position can be found here. The deadline for applications is January 15, 2019.

ERC Starting grant for Daniel Dadush

Daniel Dadush (CWI) has been awarded an ERC Starting Grant of 1.5 ME for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems.

Read more.