Programme of the DIAMANT symposium
Hotel Haarhuis, Arnhem
5 and 6 June 2014
Thursday | |
11:00-11:25 | arrival and coffee |
11:25-11:30 | welcome |
Ted Chinburg (UPenn) | Crypto Capacity Theory |
11:30-12:25 | Suppose f(x) is a monic integral polynomial of degree d and that N is a positive integer. With cryptographic applications in mind, Coppersmith showed in the 1990's that there is a polynomial time algorithm for finding all integers r such that f(r) is congruent to 0 mod N and |r| < N^{1/d}. In this talk I will discuss how Coppersmith's method is in fact a baby case of adelic capacity theory but with the additional input of the LLL theorem. This leads to a new approach to many results of this kind as well as to new variants of capacity theory. This is joint work with N. Heninger and Z. Scherr. |
12:30-14:30 | lunch |
Sam van Gool (U Bern) | Sheaves and duality for MV-algebras |
14:30-14:55 |
Infinite-valued Lukaciewicz logic is a propositional logic in which formulas can take truth values in the unit interval [0,1], rather than only the "Boolean" truth values in {0,1}. A classical result by Mundici says that the algebraic structures arising from this logic (MV-algebras) are unit intervals in certain lattice-ordered abelian groups. In particular, n-variable formulas in infinite-valued Lukaciewicz logic faithfully represent the continuous piecewise linear maps from [0,1]^n to [0,1]. In this talk, based on our recent joint work with Mai Gehrke and Vincenzo Marra (arXiv:1306.2839), we will discuss sheaf representations of MV-algebras using Stone-Priestley duality theory for distributive lattices with additional operations. In particular, we show that any sufficiently nice decomposition of the prime spectrum of the underlying lattice structure of an MV-algebra naturally leads to a sheaf representation of the MV-algebra. We also apply our analysis of two specific such decompositions to give an MV-algebraic generalization of a classical theorem by Kaplansky, which stated that two compact Hausdorff spaces are homeomorphic if, and only if, the lattices of continuous [0,1]-valued functions on the spaces are isomorphic. |
Rostislav Devyatov (UL/Berlin) | Infinitesimal equivariant deformations of a special class of affine T-varieties |
15:00-15:25 | An algebraic torus is the group of all diagonal complex matrices with nonzero entries on the diagonal. A T-variety is a normal algebraic variety with a faithful action of an algebraic torus. In my talk I will explain how to construct such varieties from combinatorial data and varieties of smaller dimension (mostly I will focus on the case when the dimensions a the T-variety and of the torus differ by 1). Then I will explain what a deformation and an infinitesimal deformation of an affine algebraic variety is and how to introduce a vector space structure on the set of all infinitesimal deformations. If the variety we deform is actually a T-variety, it is also possible to introduce an action of a torus on this vector space. If time permits, I will also say something about how to compute the dimension of the vector space of equivariant infinitesimal deformations of certain T-varieties. |
15:30-16:00 | tea |
Ariyan Javanpeykar (U Mainz) | Integral points on moduli stacks |
16:00-16:25 | Faltings proved the finiteness of the set of integral points on the moduli stack of abelian varieties. In a joint work with Daniel Loughran, we investigate the finiteness of the set of integral points on moduli stacks of complete intersections. It turns out that for complete intersections of small Hodge level, similar finiteness statements can be proven. |
Antoine Joux (Paris) | The discrete logarithm problem in small characteristic finite fields |
16:30-17:25 | In this talk, we present the discrete logarithm problem, recall its use in cryptography, and describe the effective and algorithmic methods that have been proposed to solve this problem. In particular, we will focus on the recent advances that, under some reasonable looking heuristics, allow to compute discrete logarithms in quasi-polynomial time. For simplicity of presentation, we describe a variation of the algorithms that requires fewer technicalities than the published versions. |
17:30-19.00 | drinks |
19:00 | dinner |
Friday | |
Laurence Wolsey (Louvain-La Neuve) | Cutting Planes and Extended Formulations for Single and Multi-Vehicle Inventory Routing Problems |
9:00-9:55 | The Inventory Routing Problem (IRP) involves the distribution of one or more products from a supplier to a set of customers over a discrete planning horizon. Each customer has a known demand to be met in each period and can hold a limited amount of stock. The product is shipped through a distribution network by a fleet of vehicles of limited capacity. The version treated here, the so-called Vendor Managed Inventory Routing Problem (VMIRP) is the Inventory Routing problem arising when replenishment policies are decided in advance. We consider two replenishment policies. The first is known as Order-up (OUP): if a customer is visited in a period, then the amount shipped to a client must bring the stock level up to the upper bound. The latter is called Stock Upper Bound (SUB): the stock level in each period cannot exceed the upper bound. The objective is to find replenishment decisions minimizing the sum of the storage and of the distribution costs. VMIRP contains two important subproblems: a lot-sizing problem for each client and an (almost) classical routing problem. First we introduce some new inequalities for the single period routing problem, variants that take inventory into account and multiperiod extensions. Secondly we introduce reformulations of OUP and SUB derived from the single-item lot-sizing substructure under both constant and time-varying demands. Computational results on benchmark instances with a single product and single and multiple vehicles are presented. This is joint work with Pasquale Avella and Maurizio Boccia. |
Krzysztof Dorobisz (UL) | Deformations of finite group representations |
10:00-10:25 | I will talk about the problem of lifting linear group representations over fields to representations over certain types of local rings. During last year's Symposium I discussed the question which rings can represent the associated deformation functors. As a follow-up, this time I want to address a similar problem, but restricting to representations of finite groups. Surprisingly, this slight modification requires developing completely new techniques and leads to different results. |
10:30-11:00 | coffee |
Iuliana Ciocanea (UL) | The Module Isomorphism Problem for Finite Rings and Related Results |
11:00-11:25 | Let R be a finite ring and let M, N be two finite left R-modules. We present two distinct deterministic algorithms that decide in polynomial time whether or not M and N are isomorphic, and if they are, exhibit an isomorphism. As by-products, we are able to determine the largest isomorphic common direct summand between two modules and the minimum number of generators of a module. By not requiring R to contain a field, avoiding computation of the Jacobson radical and not distinguishing between large and small characteristic, both algorithms constitute improvements to known results. We have not attempted to implement either of the two algorithms, but have no reason to believe they would not perform well in practice. |
Valentijn Karemaker (UU) | Galois representations and symplectic Galois groups over Q |
11:30-11:55 | The inverse Galois problem asks whether a given finite group can be realised as the Galois group of some finite extension of the rational field Q. We investigate Galois representations attached to the l-torsion points (where l is a prime) of principally polarised abelian varieties A/Q of genus 3. Their images lie inside the general symplectic group GSp(6,F_l) of dimension 6, with coefficients in the finite field F_l. Hence, surjective representations answer the inverse Galois problem affirmatively for this group. We will discuss the following questions: Firstly, given an abelian variety A/Q, how do we find primes l for which the corresponding representation is surjective? Secondly and conversely, given a prime l, how do we construct an abelian variety A/Q such that the associated representation is surjective? This is joint work with S. Arias-de-Reyna, C. Armana, M. Rebolledo, L. Thomas and N. Vila. |
12:00-13:00 | lunch |
Special afternoon around p-adic methods for counting points on varieties | |
David Lubicz (Rennes) | AGM, application to point counting and generalisations |
13:00-13:45 | An algorithm of Mestre uses a p-adic version of the AGM in order to count rational points on an elliptic over a finite field of characteristic 2. In this talk, we will give a brief survey of Mestre's algorithms and subsequent developments. Then we will present more recent results on generalisations of the AGM for abelian varieties of higher dimension. |
Francois Escriva (VUA) | Frobenius lifts, cup products, and point counting |
13:50-14:35 | Since Kedlaya published his algorithm for point counting on hyperelliptic curves in 2001, most research in point counting has focused on extending his algorithm to more general classes of curves. In this talk, we first present his algorithm, together with some necessary notions of p-adic analysis. Then we explain the new ideas and techniques developed in the preprint arxiv:1306.5102 (joint work with Amnon Besser and Rob de Jeu), which apply to any curve for which some auxiliary data are given. |
14:35-15:05 | tea |
Jan Tuitman (KU Leuven) |
Some recent developments in p-adic point counting |
15:05-15:50 | First, I will speak about an extension of Kedlaya's algorithm to a very general class of curves (potentially any curve) introduced in my recent preprint. This will include a demonstration of my implementation of this algorithm (the pcc_p and pcc_q MAGMA packages that can be found on my webpage). Second, if time permits, I will talk about the work of Harvey and Harvey-Sutherland on p-adic point counting in average polynomial time on hyperelliptic curves. |