Programme of the DIAMANT symposium, 24-25 November 2011



Thursday
 
11:00-11:25
arrival and coffee
11:25-11:30
opening
Etienne de Klerk Improved lower bounds on crossing numbers of graphs through optimization
11:30-12: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 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
12:30-12: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 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.
13:00-15:00
Lunch
Elisa Lorenzo The generalized Sato-Tate Conjecture for the twists of the Fermat curve
15:00-15:25
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
15:30-15:55
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.
16:00-16:30
tea
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.
17:30--19.00
drinks
19:00
dinner
   
Friday
 
Valerie Berthe
From gcd computations to discrete lines: a dynamical approach
9:00-9: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 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
10:00-10: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:30-11:00
coffee
Florian Speelman The Garden-Hose Game and Application to Position-Based Cryptography
11:00-11:25
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.
12:00-13:00
lunch
Francois-Renaud Escriva Frobenius lift and point counting
13:00-13: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:30-13: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:00-14:20 tea
Ariel Gabizon
Simple affine extractors using dimension expansion
14:20-15:15
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

Diamant symposium
29-11-2018 - 30-11-2018

Dutch Mathematical Congress 2019
23-4-2019 - 24-4-2019

News - more news

ERC Starting grant for Daniel Dadush
26-9-2018

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
26-9-2018

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
19-12-2017

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.



DIAMANT funding continued
19-12-2017

The funding of all four mathematics clusters has been continued by NWO. For the coming two years 85 kE will be available in each cluster.
Read more.