Talk abstracts, DIAMANT Symposium, May 30/31 2013, Conference Center Kapellerput, Heeze

Invited speakers (55 min talks):

Nikhil Bansal (TUE) -  On the number of matroids.

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.

Peter J.C. Dickinson (Vienna) - Applications and approximations for copositive optimisation

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).

Sam Fiorini (Brussels) - Exponential lower bounds for polytopes in combinatorial optimization, and more

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 semidefinite 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).

Koen Thas (Ghent) - Singer fields 

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.

Contributed speakers (25 min talks):

Tony Chou (TUe) - McBits: fast constant-time code-based cryptography

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.

Krzysztof Dorobisz (UL) - TBA

Ruben Hoeksma (UT) -  Two Dimensional Optimal Mechanism Design for a Sequencing Problem

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.

Lingfei Jin (CWI) - Construction of Quantum MDS codes.

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

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.

Junjiang Liu (UL) - P-adic decomposable forms inequalities

Diego Mirandola (CWI) - On powers of codes

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.

Georg Still (UT) - Linear cone programs: structure and  generic properties

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. 

Suzanne van der Ster (VU) - Assigning Sporadic Tasks to Unrelated Machines

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.

Weidong Zhuang (UL) - Reduced binary forms over function fields

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.


Mathematics cluster DIAMANT

Upcoming events

NMC 2019 and Diamant symposium
23-4-2019 - 24-4-2019

News - more news

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.

VICI grant for Nikhil Bansal

Nikhil Bansal has been awarded a Vici grant of 1.5 ME. He is one of the 35 academics to receive this grant from NWO in 2018. Bansal aims to use his grant to develop new algorithmic methods to make discrete decisions in a continuous way. He expects this to lead to applications in the fields of logistics, bio-informatics, chip design and machine learning.

Read more.

3 DIAMANT PhD positions awarded

NWO, following a shortlist provided by the DIAMANT board, has decided to award 3 PhD positions to young DIAMANT members: Dion Gijswijt (TU Delft), Jan Steffen Müller (RUG) and Arno Kret (UvA).
Read more.