Programme of the DIAMANT symposium
Conference Center Kapellerput, Heeze
30 and 31 May 2013
Thursday | |
11:00-11:25 | arrival and coffee |
11:25-11:30 | welcome |
Peter J.C. Dickinson (U VIenna) | Applications and approximations for copositive optimisation |
11:30-12:25 | During the last century, conic optimisation has been established as a useful tool with a wide range of applications. In conic optimisation, we are minimising a linear objective function subject to some linear constraints and a cone constraint. In this talk, we will look at a special type of conic optimisation called copositive optimisation. For this type of conic optimisation, the cone that we are considering is the cone of copositive matrices. This provides numerous applications, and in the first half of this talk we shall look at a new proof for how the NP-hard problem of finding the stability number of a graph can be reformulated as a copositive optimisation problem. From this we get that copositive optimisation is NP-hard. Due to this difficulty, when considering a copositive optimisation problem, we often replace the copositive cone with a simpler approximation of it. For the second half of this talk, we shall consider some new results on a sum-of-squares based class of inner approximations called the Parrilo cones. Joint work with Mirjam Dür (Universität Trier), Luuk Gijben (Rijksuniversiteit Groningen) and Roland Hildebrand (Université Joseph Fourier). |
Suzanne van der Ster (VU) | Assigning Sporadic Tasks to Unrelated Machines |
12:30-12:55 |
We study the problem of assigning sporadic tasks to unrelated machines such that the tasks on each machine can be feasibly scheduled. The hardness of this problem motivates the study of approximate feasibility tests. We present a polynomial-time algorithm which approximates the problem with a constant speedup factor of 8 + 2\sqrt(6) < 12.9. That is, the algorithm decides whether a given task system can be partitioned over the machines such that the machines can feasibly schedule these tasks while running at speed 8 + 2\sqrt(6), or that no such partition exists if the machines run at unit speed. Key to these results are two new relaxations of the demand bound function, the function that yields a sufficient and necessary condition for a task system on a single machine to be feasible. In particular, we present new methods to approximate this function to obtain useful structural properties while incurring only bounded loss in the approximation quality. Further, we employ a very general rounding procedure for linear programs (LPs) which model assignment problems with capacity-type constraints. It ensures that the cost of the rounded integral solution is no more than the cost of the optimal fractional LP solution and the capacity constraints are violated only by a bounded factor, depending on the structure of the matrix that defines the LP. In fact, our rounding scheme generalizes the well-known 2-approximation algorithm for the generalized assignment problem due to Shmoys and Tardos. |
13:00-14:30 | lunch |
Lingfei Jin (CWI) | Construction of Quantum MDS codes. |
14:30-14:55 | The construction of quantum MDS codes has attracted great interests since quantum codes were introduced. Quantum MDS codes with length up to q+1 can be constructed from classical Euclidean self-orthogonal codes. However, it is a more challenging task to construct quantum MDS codes with length n>q+1. We show how to construct quantum MDS codes with length q+1<n<q^2+1 from classical Hermitian self-orthogonal generalized Reed-Solomon codes. |
Robert Krone (TUe) | Noetherianity for infinite-dimensional toric varieties |
15:00-15:25 | Given a family of varieties which are symmetric under some group action on the variables, a natural question to ask is whether the set of defining equations stabilizes up to symmetry as the number of variables tends to infinity. We answer this question in the affirmative for a broad class of toric varieties. Our tools include well-partial-orders and combinatorics of bipartite matchings. |
15:30-16:00 | tea |
Weidong Zhuang (UL) | Reduced binary forms over function fields |
16:00-16:25 | Birch and Merriman (1972) proved that there are only finitely many GL(2,Z)-equivalence classes of binary forms in Z[X,Y] with given degree and given non-zero discriminant. Evertse proved that every binary form F in Z[X,Y] of degree n >2 with discriminant D(F) non-zero is equivalent to a binary form F* with height H(F*) < C(n,L)|D(F)|^{21/(n-1)}, where L is the splitting field of F over Q. However, the constant C(n,L) is not effective, since the proof of this result is based on the Thue-Siegel-Roth-Schmidt theory from Diophantine approximation, which is ineffective. My ongoing work is to prove a fully effective analogue over function fields, based on Mason's abc-theorem. I will talk about my results over the polynomial ring k[t], where k is an algebraically closed field of characteristic 0. |
Koen Thas (U Ghent) | Singer fields |
16:30-17:25 | It is a classical insight, going back to the 1950s in work of Tits, that one can interpret projective spaces (and, more generally, spherical buildings) and their automorphism groups over the nonexisting "field with one element". As such, the symmetric groups become Chevalley groups over this "field". Later, several scheme theories in characteristic one have been suggested (by work of, a.o., Connes and Consani, Deitmar, Lorscheid). One of the main motivations of all this work is a prediction which stems from combined work of Deninger and Manin which describes a possible path to solving the classical Riemann Hypothesis. Very recently, motivated by a quest to better understand the structure of the adèle class space of a global field in characteristic zero (and the zeroes of Riemann's zeta), Connes and Consani initiated a theory of hyperfield extensions of the so-called "Krasner hyperfield", which is one of the realizations of the field with one element. A deep connection appears with certain group actions on certain combinatorial geometries. In my talk, I plan to elaborate on brand new results in this theory, make wild speculations and pose several open questions on the way. |
17:30-19.00 | drinks |
19:00 | dinner |
Friday | |
Sam Fiorini (U Brussels) | Exponential lower bounds for polytopes in combinatorial optimization, and more |
9:00-9:55 | Linear programming is a powerful and widely used tool for tackling problems throughout Computer science and Mathematics. Despite the importance of linear programming, both in practice and theory, we do not have a good understanding of what problems can be efficiently expressed as linear programs (LPs). I will lift part of the veil and explain how to prove that there exist problems, such as the traveling salesperson problem (TSP), that need exponential size LPs. More precisely, our result states that every polytope that projects to the TSP polytope is defined by an exponential number of linear constraints. This result solves a 20-year old problem posed by Yannakakis. It was discovered through a new connection that we made between one-way quantum communication protocols and semideﬁnite programming reformulations of LPs. This is is joint work with S. Massar (Brussels), S. Pokutta (Georgia Tech), H.R. Tiwary (Brussels), R. de Wolf (CWI). I will then explain how to extend these results in the context of approximation algorithms. There we proved tradeoffs between the size and the approximation factor of LPs for the unweighted CLIQUE problem. This is joint work with G. Braun (Georgia Tech), S. Pokutta (Georgia Tech) and D. Steurer (Cornell). |
Junjiang Liu (UL) | P-adic decomposable form inequalities |
10:00-10:25 | Thunder's paper in 2001 gives several results about the finiteness of the solutions to decomposable form inequalities which confirms a conjecture by Schmidt. In this talk, I will present our result (with Evertse) about the generalization of Thunder's results to their P-adic cases. In particular, I will concentrate on the Norm form case which is a special case of decomposable forms. |
10:30-11:00 | coffee |
Tony Chou (TUe) | McBits: fast constant-time code-based cryptography |
11:00-11:25 | This talk presents extremely fast algorithms for code-based public-key cryptography, including full protection against timing attacks. For example, our software achieves a reciprocal throughput of just 36615 cycles per decryption at a 80-bit security level on a single Ivy Bridge core. These algorithms rely on an additive FFT for fast root computation, a transposed additive FFT for fast syndrome computation, and a sorting network to avoid cache-timing attacks. |
Diego Mirandola (UL, CWI) | On powers of codes |
11:30-11:55 | Given a linear code C, one can define the d-th power of C as the span of all componentwise products of d elements of C. A power of C may quickly fill the whole space. Our purpose is to reply to the following question: does the square of a code ''typically" fill the whole space? We show that this is the case, when the codes have dimension larger than the square root of the length. In our proof we need results about the number of zeros of quadratic forms. Finally we discuss the implications on multiplicative secret sharing. Joint work with Ignacio Cascudo, Ronald Cramer, Gilles Zemor. |
12:00-13:00 | lunch |
Georg Still (UT) | Linear cone programs: structure and generic properties |
13:00-13:25 | In this talk we consider linear cone programming, an important class of convex optimization problems. It contains linear programming (LP), semidefinite, and copositive programming as special cases. We introduce the duality concept and discuss the generic structure of conic programs. In our exposition we say that a property is generic if it holds for almost all problem instances and if the property is stable with respect to small perturbations of the problem data. The following main points will be treated: The generic structure of LP is compared with the structure of general conic programming. It appears that strong duality is a generic property in general cone programming and that unicity and strict complementarity of the solutions holds for almost all such problems. It will be shown how the generic structure of LP can be analysed by methods from (smooth) differential geometry. On the other hand, general cone programs cannot be treated as smooth problems but have to be studied by techniques from (nonsmooth) geometric measure theory. |
Ruben Hoeksma (UT) | Two Dimensional Optimal Mechanism Design for a Sequencing Problem |
13:30-13:55 | I present results on optimal mechanism design for a sequencing problem where the jobs' processing times and waiting costs are private. Given public priors for jobs' private data, we seek to find a scheduling rule and incentive compatible payments that minimize the total expected payments to the jobs. Here, incentive compatible refers to a Bayes-Nash equilibrium. While the problem can be efficiently solved when jobs have single dimensional private data, we here address the problem with two dimensional private data. We show that the problem can be solved in polynomial time by linear programming techniques. Our implementation is randomized and truthful in expectation. The main steps are a compactification of an exponential size linear program, and a combinatorial algorithm to decompose feasible interim schedules. |
14:00-14:30 | tea |
Krzysztof Dorobisz (UL) |
Inverse problem for the deformations of group representations |
14:30-14:55 |
The deformation theory deals with the question of lifting linear group representations over fields to representations over certain types of local rings. Barry Mazur's results from the 1980's state that, roughly speaking, given a continuous representation of a profinite group over a finite field, its deformation behaviour is "controlled" by the so called universal deformation ring. In my talk I will first make this statement precise and then discuss my results regarding the following problem: which rings do occur as the universal deformation rings? |
Nikhil Bansal (TUe) | On the number of matroids |
15:00 - 15:55 | I will talk about some recent results on upper bounding the number of matroids on a ground set of size n. The talk will consist of two parts. First, I will describe a technique for bounding the number of stable sets in a graph, where one uses the spectral properties of the graph to represent every stable set using few bits. Second, we will see how this idea, together with some basic properties of matroids, can be used to obtain a compressed representation for any matroid. Our bound substantially improves the previous results and comes quite close to the known lower bound on the number of matroids. Joint work with Rudi Pendavingh and Jorn van der Pol. |