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
1-6-2017 - 2-6-2017

Diamant symposium
30-11-2017 - 1-12-2017

NMC / Diamant symposium
3-4-2018 - 4-4-2018

News - more news

NWO Call for Tenure Track positions
22-7-2016

NWO has opened a call for tenure track positions. Proposals for these positions, which include one PhD position for each tenure track position, can be submitted directly to NWO by professors from the 4 mathematics clusters, including Diamant. Diamant professors are warmly encouraged to submit proposals. Read more.



Dion Gijswijt and Jordan Ellenberg independently substantially improve capset bound
25-5-2016

A capset in a finite dimensional vector space over the field with 3 elements is a subset that contains no 3-term arithmetic progressions. Dion Gijswijt (TU Delft) and Jordan Ellenberg have independently obtained a bound on the size of a capset that for the first time improves substantially on the trivial bound 3^n. Read more in Terence Tao's blog about these developments.



Harry Buhrman lectures on quantum computing in Universiteit van Nederland
21-1-2015

Starting 12 January 2015, the Universiteit van Nederland publishes five public lectures by Harry Buhrman, head of the research group quantum computing at CWI. The series of lectures features the do's and don'ts of the computer of the future. From Monday through Friday, a new lecture will be available on the site of the Universiteit van Nederland each day.



Monique Laurent, Nikhil Bansal and Ronald de Wolf receive TOP-grant
12-12-2013

Monique Laurent, Nikhil Bansal and Ronald de Wolf have received a TOP-grant from NWO for their joint project "Approximation Algorithms, Quantum Information and Semidefinite Optimization". Read more.