DIAMANT Intercity Seminar

Fridays 2 and 9 February 2007

Place

All talks take place in the DIAMANT seminar room: 9.41 in the main building building (HG) at the TU/e in Eindhoven (map of campus, travel directions). Coffee is served in the adjacent DIAMANT lounge: 9.42.

Programme

Friday 2 February

10:00-10:30 Coffee/Tea
10:30-11:15 Péter Csorba On the Topological Lower Bound for the Chromatic Number
Coloring graphs is a notoriously difficult problem. Using some topology might be useful and interesting.
11:15-12:00 Yu Xia A continuous approach to data partition
We use a continuous approach to solve the clustering (data partition) problem which is a nonlinear zero-one integer program.
12:00-13:30 Lunch (not included)
13:30-14:15 Bas Spitters Hilbert's program and the algebraization of analysis
Hilbert's basis theorem asserts the existence of a finite set of generators without any indication of how to actually find them. Gordan rejected Hilbert's proof for the Mathematische Annalen, asserting it was theology, not mathematics. The following debate about what counts as a valid proof lead to a foundational crisis in mathematics. This debate faded away, but the question `what is a valid proof' was never resolved, most mathematicians simply got used to `theology'. Fortunately, Hilbert himself already proposed a solution. He developed a program to reduce `theology' to finitary mathematics. Often one can replace ideal objects, such as real numbers or maximal ideals, by finitary approximations to them using rational intervals and (non-maximal) ideals, thus translating the theorem into a finitary setting. I will highlight how parts of this program can be carried out in a systematic way. Then I will indicate how it connects to recent topics in computer mathematics, quantum computation and proof mining. As an illustration of the latter we will show how to mechanically remove the axiom of choice from certain parts of analysis by translating them into algebra.
14:15-15:00 Lenny Taelman Galois Theory for Transcendental Numbers?
I shall sketch what doing Galois Theory with transcendental numbers should be like, and also, I shall show why in characteristic $p$ it is actually possible.
15:00-15:15 Coffee/Tea
15:15-16:00 Danny Harnik The Power of the Randomized Iterate
In this talk I will present a technique known as the randomized iterate and survey some of its intriguing applications to a very central problem in cryptography - basing pseudorandom generators on one-wayness.
16:00 drink in DIAMANT lounge

Friday 9 February

10:00-10:30 Coffee/Tea
10:30-11:15 Mridul Nandi A view on Indistinguishability, A popular security notion in Symmetric Cryptography
In this seminar, I would like to present how one can make an indistinguishability security analysis in a concrete and simple way. Intuitively, indistinguishability means that it is difficult to distinguish between two classes of ob jects, say two families of functions. Most of the literatures regarding indistinguishability have been made by using game playing approach. In this talk, I would present a mathematically concrete analysis which can be made in a simpler way than the game playing techniques. I would also like to point out that many well known proofs contain serious mistakes. I have proved many well known results (including the result containing mistakes) by the concrete framework for indistinguishability. I have also found several modified results. For example,
  1. more efficient online ciphers than existing ones,
  2. a wider class of DAG based PRF which contains many constructions like PMAC, XCBC, TMAC, OMAC,
  3. an improved security bound for PMAC and
  4. indifferentiability for several designs of hash functions including double block length hash functions and EMD hash functions.
  5. Thus I have unified many indistinguishability results and put into a common framework (as much as possible) and have provided a concrete and simple security analysis. I expect this direction of research would help us to have many more interesting results in future.
11:15-12:00 John P. Steinberger Tilings and Vanishings
The speaker will present some of his results on translational tilings of the integers by finite sets and their connection to vanishing sums of roots of unity.
12:00-13:30 Lunch (not included)
13:30-14:15 Peter Malkin Groebner bases and Markov bases of Integer Programs
I will present new algorithms for computing Groebner bases and Markov bases of integer programs, which are in general much faster than previous methods.
14:15-15:00 Enav Weinreb Secret Sharing Schemes - Complexity Issues and Constructions
Secret sharing schemes enable a dealer to share a secret among a set of players such that only some predetermined subsets of the players can reconstruct the secret from their shares. Most of the known secret sharing schemes are designed using linear algebraic techniques. We prove that non-linear secret sharing schemes are stronger than their linear counterparts, and show some efficient constructions of secret sharing schemes.
15:00-15:15 Coffee/Tea
15:15-16:00 Benjamin Kane Computationally Feasible Bounds for Quadratic Forms and CM Lifts of Supersingular Elliptic Curves
For a supersingular elliptic curve E, we use a correspondence between lifts to elliptic curves with CM by O_{-D} and representations of D by a certain quadratic form to show an explicit bound D_E, conditional upon GRH, for which a lift exists whenver D>D_E.
16:00 Informal drinks in DIAMANT room

Further information

There is no registration, and participation is free. Contact Jan Draisma for more information.