Programme of the Diamant symposium

June 1 and 2 2017
Hotel Van der Valk, Breukelen

11:00-11:25 arrival and coffee
11:25-11:30 welcome
Cristóbal Guzmán (Universidad Católica de Chile/CWI) Great Tolls: How to induce optimal flows under strategic link owners
Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: users of the network and owners of the network. Owners of the network post a price for usage of the link they own; users of the network select routes based on price and level of use by other users. The challenge in these games is that there are two levels of competition: one, among the owners to attract users to their link so as to maximize profit; and second, among users of the network to select routes that are cheap yet not too congested. Interestingly, we observe that: (i) an equilibrium may not exist; (ii) it might not be unique; and (iii) the network performance at equilibrium can be arbitrarily inefficient. Our main result is to observe that a slight regulation on the network owners market solves all three issues above. Specifically, if the authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge then: the game among the link operators has a unique strong Nash equilibrium and the users’ game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls. We then ask, can we compute great tolls that minimize total users’ payments? We show that this optimization problem reduces to a linear program in the case of single-commodity series-parallel networks. Starting from the same linear program, we obtain multiplicative approximation results for arbitrary networks with polynomial latencies of bounded degree, while in the single-commodity case we obtain a surprising bound, which only depends on the topology of the network. This is joint work with José Correa, Thanasis Lianeas, Evdokia Nikolova and Marc Schröder.
12:30-13:30 lunch
David de Laat (CWI) Using (noncommutative) polynomial optimization to bound matrix factorization ranks
13:30-13:55 In this talk I will explain how polynomial optimization can be used to compute lower bounds on matrix factorization ranks. First I will show how we can use noncommutative polynomial optimization to compute lower bounds on the cpsd-rank (completely positive semidefinite rank) of a matrix. The cpsd-rank of a matrix A is the smallest integer d for which A can be written as the Gram matrix of positive semidefinite d by d matrices. Then I will show how we can use these ideas to also compute lower bounds on the cp-rank and nonnegative rank of a matrix, and I will compare this to existing techniques.
Chloe Martindale (TUe) Constructing genus 2 curves with a prescribed number of points
14:00-14:25 We will give a definition of class polynomials for genus 2 curves, and show how they are used to construct genus 2 curves with a prescribed number of points. We give a new algorithm to compute class polynomials for genus 2 curves, and explain briefly the applications to cryptography.
Mark Jones (TUD) Constructing a consensus phylogeny from a leaf-removal distance
14:30-14:55 Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. In this talk, we are given a set of phylogenetic trees that describe conflicting evolutionary histories for a set of species, and our task is to find a single tree that agrees with the input trees as much as possible. We study a few variants of this problem, where disagreement between two trees is measured by the number of leaves that need to be deleted before the trees become identical. At the end of the talk, we'll briefly discuss how the situation becomes more complex when phylogenetic trees are generalised to phylogenetic networks.
15:00-15:30 tea
Guido Lido (UL, Roma Tor Vergata) Discrete logarithms in finite fields of small characteristic
15:30-15:55 Given a finite field K a generator of g of K^* and another element h of K^*, solving the discrete logarithm problem consists of finding an integer x ∈ Z such that g^x = h. Its connection to many cryptographic protocols has motivated a large amount of research intended to find efficient algorithms to solve this problem. Recently the work of A. Joux has led to algorithms significantly faster than the previous ones over “many” finite fields of small characteristic (i.e. finite fields whose characteristic is much smaller than the cardinality). These algorithms have quasi-polynomial complexity and work over finite fields of small characteristic admitting a particular kind of presentation. Unfortunately it is not known which finite fields admit this kind of presentation, thus it is not proven that these algorithms can be applied in all the finite fields of small characteristic. In the talk we will define a new kind of presentation for finite fields, based on elliptic curves, and we will describe a new algorithm, based on Joux’s ideas, that works over finite fields admitting a presentation of this new kind. This algorithm is also quasi-polynomial and it is easy to prove that it can actually be applied to all finite fields of small characteristic.
Diane Maclagan (Warwick) Valuated matroids in tropical geometry
16:00-16:55 Tropical geometry allows algebraic varieties to be studied using combinatorial and polyhedral techniques.  In this talk I will highlight the role of matroids in tropical geometry, with a particular emphasis on joint work with Felipe Rincon, in which we use valuated matroids to define a subscheme of a tropical toric variety, building on work of Jeff and Noah Giansiracusa on tropicalizing subschemes.  No knowledge of either matroids or tropical geometry will be assumed.
17:00-18.30 drinks
18:30 dinner
Benjamin Nill (U Magdeburg) The geometry of numbers of lattice polytopes
9:30-10:25 A lattice polytope is a polytope whose vertices have integer coordinates. Their study has grown into a very active field of research at the crossroads of convex, discrete and toric geometry, integer optimization, commutative algebra and enumerative combinatorics. In this survey talk, I will give an overview of recent developments in this research area. I will motivate where the ongoing interest in lattice polytopes comes from, what methods are used in their studies, and what the challenges are we cannot yet overcome. In particular, I will talk about current work to find sharp volume bounds, the continuing classification of lattice polytopes without interior lattice points, and the ongoing quest to understand their most important invariant - the Ehrhart polynomial - that counts the number of lattice points in their dilates.
10:30-11:00 coffee
Leon Groot Bruinderink (TU/e) Improving Side-channel Attacks on Lattice-based Cryptography
11:00-11:25 In the search for post-quantum secure alternatives to RSA and ECC, lattice-based cryptography appears to be an attractive and efficient option. A particularly interesting lattice-based signature scheme is BLISS, offering key and signature sizes in the range of RSA moduli. A range of works on efficient implementations of BLISS is available, and the scheme has seen  a first real-world adoption in strongSwan, an IPsec-based VPN suite. In contrast, the implementation-security aspects of BLISS, and lattice-based cryptography in general, are still largely unexplored. At CHES 2016, Groot Bruinderink et al. presented the first side-channel attack on BLISS, thus proving that this topic cannot be neglected. Nevertheless, their attack has some limitations. First, the technique is demonstrated via a proof-of-concept experiment that was not performed under realistic attack settings. Furthermore, the attack does not apply to BLISS-B, an improved variant of BLISS and also the default option in strongSwan. This problem also applies to later works on implementation security of BLISS. In this work, we solve both of the above problems. We present a new side-channel key-recovery algorithm against both the original BLISS and the BLISS-B variant. Our key-recovery algorithm  draws on a wide array of techniques, including learning-parity with noise, integer programs, maximimum likelihood tests, and a lattice-basis reduction. With each application of a technique, we reveal  additional  information on the secret key culminating in a complete key recovery. Finally, we show that cache attacks on post-quantum cryptography are not only possible, but also practical. We mount an asynchronous cache attack on the production-grade BLISS-B implementation of strongSwan. The attack recovers the secret signing key after observing roughly 6,000 signature generations.
Milan Lopuhaä (RU) Integral forms of reductive algebraic groups
11:30-11:55 Let G be a reductive algebraic group over a number field or a p-adic field K with ring of integers R, and let V be a faithful representation of G. Then a lattice L in V (i.e. a locally free R-submodule of maximal rank) determines a model of G over R. One may wonder to what extent one can recover L if this model is known. In this talk I will show that, up to some natural equivalence relation, there are only finitely many lattices yielding the same integral model.
12:00-13:00 lunch
Christine van Vredendaal (TU/e) Finding short generators in multiquadratic number fields
13:00-13:25 Finding a short element g of a number field, given the ideal generated by g, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, Smart-Vercauteren, Gentry-Halevi, Garg-Gentry-Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low post-quantum security level i.e. can be solved in polynomial time with a quantum computer. In this talk I will show that for multiquadratic number fields this problem can be solved in quasi-polynomial time without a quantum computer.
Anna Somoza Henares (UL, UPC Barcelona) Construction of Picard curves with CM
13:30-13:55 The Schottky problem wonders about which principally polarized abelian varieties arise as Jacobians of curves. There exists a natural morphism between the moduli space of curves of genus g and the moduli space of principally polarized abelian varieties of dimension g, so by counting dimensions one realizes that the Schottky problem has a positive answer for g ≤ 3. However, we can still consider the effective version of the question, which seeks to determine such a curve whenever there is one. There are methods for the construction of such curves in genus 2 and genus 3, when assuming that the curve has complex multiplication by the maximal order of a certain field. In this talk we will see the current situation for genus 3 and we will focus on the family of Picard curves, giving a conjectural list of models defined over Q and possible generalizations of the method.
14:00-14:30 tea
Neil Olver (VU) Generalized flow, the net present value problem, and an open question in arithmetic computation
14:30-15:25 The maximum generalized flow problem is a classical generalization of maximum flow where flow is scaled as it traverses each arc, and has been intensively studied for the past few decades. Only very recently, Végh gave a "strongly polynomial" algorithm for this problem - an algorithm that is efficient in a certain refined sense. We give a new strongly polynomial algorithm that is both substantially faster and dramatically simpler. I will discuss the implications of our result to a classical problem in project scheduling, and a seemingly basic open algorithmic question in arithmetic that our work brings to light. (Includes joint work with L. Végh, as well as J. Correa, A. Schulz and L. Végh).
15:30 end of the symposium




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.