Programme of the DIAMANT symposium, 24-25 November 2011

arrival and coffee
Etienne de Klerk Improved lower bounds on crossing numbers of graphs through optimization
The crossing number problem for graphs is to draw (or embed) a graph in the plane with a minimum number of edge crossings. Crossing numbers are of interest for graph visualization, VLSI design, quantum dot cellular automata, RNA folding, and other applications.
On the other hand, the problem is notoriously difficult. In 1973, Erdös and Guy wrote that: "Almost all questions that one can ask about crossing numbers remain unsolved." For example, the crossing numbers of complete and complete bipartite graphs are still unknown. The case of the complete bipartite graph is known as Turán's brickyard problem, and was already posed by Paul Turán in the 1940's. Moreover, even for cubic graphs, it is NP-hard to compute the crossing number.
Different types of crossing numbers may be defined by restricting drawings; thus the two-page crossing number corresponds to drawings where all vertices are drawn or a circle, and all edges either inside or outside the circle. It is conjectured that the two-page and normal crossing numbers coincide for complete and complete bipartite graphs. In this talk, we will survey some recent results, where improved lower bounds were obtained for (two-page) crossing numbers of complete and complete bipartite graphs through the use of optimization techniques.
Thijs Laarhoven Dynamic Tardos Traitor Tracing Schemes
To protect digital content from unauthorized redistribution, distributors embed watermarks in the content to link copies to users. By cooperating and combining their watermarks, several colluders can create a copy which has a watermark that is different from each of their individual watermarks. We present a new traitor tracing scheme, resistant against such collusion-attacks, which improves upon earlier results from the literature. This scheme builds upon the well-known Tardos scheme, and translates the problem of distinguishing between colluders and innocent users to a problem of distinguishing between biased and unbiased random walks.
Elisa Lorenzo The generalized Sato-Tate Conjecture for the twists of the Fermat curve
The original Sato-Tate conjecture for elliptic curves is solved in almost all the cases. Recently, some mathematicians from the MIT and the UPC have done a deep study for the dimension 2 case. Now, I am working in a special subcase of the dimension 3 case. I have computed all the twists of the Fermat curve over the rational numbers, the distribution of the trace of the Frobenius endomorphisms on them and I have checked that they coincide with the distribution of the trace of the elements in its associated Sato-Tate groups. In this way I check the conjecture for these cases.
M. Stevens  The problem about SHA-1 collisions
MD5 and SHA-1 are both widely used cryptographic hash functions that map any message of arbitrary bit length to a hash value of fixed small bit length. The security of MD5 was broken in 2004 when a collision was constructed: two messages with the same hash. The MD5 collision attack complexity dropped from 240 hash computations to 216 in just 5 years. SHA-1, the successor of MD5, was broken in 2005 due to a theoretical attack with a complexity of 269 hash computations. Despite many results and claims, there have been no published improvements so far... We share some new insights into the analysis of SHA-1 by presenting a new versatile technique. We also present a SHA-1 near-collision attack and bounds on the SHA-1 collision attack complexity.
Dan Bernstein
Jet list decoding
16:30-17:25 One can efficiently interpolate an integer from its remainders modulo enough primes. If there are more primes than necessary then one can tolerate some erroneous remainders. The classic error-correction algorithms limit the product of the erroneous primes to about the square root of the product of the extra primes, but more sophisticated algorithms use lattice-basis reduction to go beyond this limit. I will discuss a new wave of algorithms that achieve the same effect using much more streamlined lattices. I plan to emphasize the function-field case, and in particular the important case of Goppa codes. No prior exposure to coding theory is required.
Valerie Berthe
From gcd computations to discrete lines: a dynamical approach
As a motivation,  we first consider the following question: how to discretize a line in the space? This will lead us in a natural way to the related  problem of the computation of the gcd of three or more numbers, and to its average-case analysis. Discrete lines are perfectly well understood in the plane and can be very efficiently described by means of regular continued fractions and Euclid's algorithm. But the lack of a canonical multidimensional generalization of Euclid's algorithm makes the question much more difficult to handle in the space. There is also a further difficulty if one wants to work with integer parameters, which is natural in discrete geometry. Indeed, the ergodic approach is a priori not relevant when working with parameters that belong to a zero measure set. Nevertheless, the aim of this lecture is to show which answers can be provided thanks to the use of techniques issued from Dynamical Analysis together with fusion algorithms obtained by combining known classical multidimensional continued fraction algorithms.
Dion Coumans  Generalizing canonical extension to the categorical setting
In the 1950s Jonsson and Tarksi introduced the notion of canonical extension of a Boolean algebra with operators. By now, the theory of canonical extensions has been developed further and it has proven to be a powerful tool in the study of propositional logics. I'll present a generalization of this theory to the categorical setting by describing a notion of canonical extension for coherent categories, the categorical analogue of distributive lattices. This opens the door to the applications in the study of first order logics.
Florian Speelman The Garden-Hose Game and Application to Position-Based Cryptography
We study position-based cryptography in the quantum setting. We examine a class of protocols that only require the communication of a single qubit and 2n bits of classical information. To this end, we define a new model of communication complexity, the garden-hose model, which enables us to prove upper bounds on the number of EPR pairs needed to attack such schemes. This model furthermore opens up a way to link the security of quantum position-based cryptography to traditional complexity theory. 
Michiel Kosters
The subset sum problem for finite abelian groups
11:30-11:50 Let G be a finite abelian group of size n. For g in G and i with 0 ≤ i ≤ n we want to compute N(i,g)=#{S ≤G: #S=i, Σs in S s=g}. During the lecture we present a formula which allows one to compute these N(i,g) in polynomial time in n.
Francois-Renaud Escriva Frobenius lift and point counting
Efficient point counting algorithms for algebraic curves over finite fields are only designed for special kinds of curves: hyperelliptic curves, C_{a,b} curves, etc. Currently, the algorithm which seems to be the most general covers the nondegenerate case, which still restricts the kind of curves one can study. In this talk we will see how it is possible to give an explicit lift (with estimates for the radius of overconvergence) of the Frobenius endomorphism of a curve (and of a variety of higher dimension) in greatest generality and how it can be applied to point counting.
Ane Anema Branched covering spaces of elliptic curves
We will focus on branched covering spaces of elliptic curves that branch above a single point. In particular we give examples of such spaces using methods from algebraic geometry.
14:00-14:20 tea
Ariel Gabizon
Simple affine extractors using dimension expansion
Let F be the finite field of q elements. An (n,k)-affine extractor is a coloring of Fn with 2 colors, such that every affine subspace of dimension at least k in Fn is colored in a balanced way. In this work, we explicitly construct affine extractors roughly whenever q > (n/k)2, provided that F has characteristic at least n/k. Our proof uses a result of Heur, Leung, and Xiang giving a lower bound on the dimension of a 'product' of subspaces. I will present this result of [HLX] in the hope that it could be useful elsewhere in combinatorics and theoretical computer science. Joint work with Matt DeVos.

Mathematics cluster DIAMANT

Upcoming events

NMC 2020 and Diamant symposium CANCELLED
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.