Programme of the DIAMANT symposium, 2425 November 2011
Thursday 

11:0011:25 
arrival and coffee 
11:2511:30 
opening 
Etienne de Klerk  Improved lower bounds on crossing numbers of graphs through optimization 
11:3012:25 
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 NPhard to compute the crossing number. Different types of crossing numbers may be defined by restricting drawings; thus the twopage 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 twopage 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 (twopage) crossing numbers of complete and complete bipartite graphs through the use of optimization techniques. 
Thijs Laarhoven  Dynamic Tardos Traitor Tracing Schemes 
12:3012:55 
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 collusionattacks, which improves upon earlier results from the literature. This scheme builds upon the wellknown Tardos scheme, and translates the problem of distinguishing between colluders and innocent users to a problem of distinguishing between biased and unbiased random walks. 
13:0015:00 
Lunch 
Elisa Lorenzo  The generalized SatoTate Conjecture for the twists of the Fermat curve 
15:0015:25 
The original SatoTate 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 SatoTate groups. In this way I check the conjecture for these cases. 
M. Stevens  The problem about SHA1 collisions 
15:3015:55 
MD5 and SHA1 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 2^{40} hash computations to 2^{16} in just 5 years. SHA1, the successor of MD5, was broken in 2005 due to a theoretical attack with a complexity of 2^{69} hash computations. Despite many results and claims, there have been no published improvements so far... We share some new insights into the analysis of SHA1 by presenting a new versatile technique. We also present a SHA1 nearcollision attack and bounds on the SHA1 collision attack complexity. 
16:0016:30 
tea 
Dan Bernstein 
Jet list decoding 
16:3017: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 errorcorrection 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 latticebasis 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 functionfield case, and in particular the important case of Goppa codes. No prior exposure to coding theory is required. 
17:3019.00 
drinks 
19:00 
dinner 
Friday 

Valerie Berthe 
From gcd computations to discrete lines: a dynamical approach 
9:009:55 
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 averagecase 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 
10:0010:25 
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. 
10:3011:00 
coffee 
Florian Speelman  The GardenHose Game and Application to PositionBased Cryptography 
11:0011:25 
We study positionbased 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 gardenhose 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 positionbased cryptography to traditional complexity theory. 
Michiel Kosters 
The subset sum problem for finite abelian groups 
11:3011: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. 
12:0013:00 
lunch 
FrancoisRenaud Escriva  Frobenius lift and point counting 
13:0013:25 
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 
13:3013:55 
_{}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:0014:20  tea 
Ariel Gabizon 
Simple affine extractors using dimension expansion 
14:2015:15 
Let F be the finite field of q elements. An (n,k)affine extractor is a coloring of F^{n} with 2 colors, such that every affine subspace of dimension at least k in F^{n} 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. 