Talk abstracts, DIAMANT Symposium, November 29/30 2012, Conference Center Kaap Doorn, Doorn
Invited speakers (55 min talks):
Craig Gentry (IBM) -
Gunnar Klau (CWI) - Operations Research in the Cell
Companies and cells face similar problems: the effective use of scarce resources under dynamic and uncertain conditions, which is also a good definition of the interdisciplinary field of Operations Research. Because of this analogy, methods from Operations Research are also helpful to understand biology.
This talk illustrates how methods from discrete optimization can be used to solve different problems in bioinformatics such as the identification of cancer modules and the alignment of biological networks.
Hugues Randriambololona (ENST Paris) - Asymptotically good codes with asymptotically good squares
Define the square of a linear code (sometimes also called its Schur transform) as the linear span of products of pairs of codewords under coordinatewise multiplication. A possible motivation for the study of this notion can be found in the theory of secure multi-party computation. In this talk we prove that for any alphabet size q (and in particular for q=2) there
exists asymptotically good codes whose squares are also asymptotically good. When q is big, it is easy to show that algebraic-geometry codes satisfy this property. And when q is small, this can also be done by first working over an extension field and then descend to the base field by concatenation. However, as simple as it may sound, to estimate the distance of the
squared concatenated code will require surprisingly intricate arguments ranging from considerations in bilinear algebra to a recent result on the number of points on curves over non-square fields.
Gilles Zémor (Université Bordeaux 1) - (More) efficient oblivious transfer from noisy channels.
Crépeau and Kilian first showed how to achieve unconditionally secure oblivious transfer protocols between potentially dishonest parties that share a noisy channel. We discuss how some new ideas from coding theory yield improved protocols: a crucial notion is, for a given linear code C, the linear code generated by the componentwise products of codewords of C.
Joint work with Frédérique Oggier.
Sander Zwegers (Universitat Koeln) - An Introduction to Nahm's Conjecture
We consider certain q-series depending on parameters (A,B,C), where A is a positive definite r times r matrix, B is a r-vector and C is a scalar, and ask when these q-series are modular forms. Werner Nahm (DIAS) has formulated a partial answer to this question: he conjectured a criterion for which A's can occur, in terms of torsion in the Bloch group. For the case r=1, the conjecture has been show to hold by Don Zagier (MPIM and CdF), but for r>1 counterexamples have been found. In this talk we'll discuss various aspects of Nahm's conjecture.
Contributed speakers (25 min talks):
Evan de Corte (TU Delft) - Independent sets in measurable graphs
Consider a graph whose vertex set is a Borel probability space and whose edge set is Borel, and define the independence ratio of the graph as the supremum of the measures of its independent sets. Inspired by techniques from combinatorial optimization, we discuss various ways to estimate this number and we calculate it exactly for a few examples.
Ross Kang (CWI) - For almost all graphs H, almost all H-free graphs have a linear homogeneous set.
There have been various structural attacks upon a conjecture of Erdos and Hajnal from extremal graph theory. This notorious open problem is concerned with understanding how the exclusion from G a fixed graph H as an induced subgraph affects the maximum size of a homogenous set (a clique or stable set) in G. I will focus on recent asymptotic, probabilistic formulations of the conjecture, proved using Szemeredi regularity, one of which is joint work with Colin McDiarmid, Bruce Reed and Alex Scott.
David de Laat (TU Delft) - A semidefinite programming hierarchy for geometric packing problems
How can one pack spherical caps of certain given sizes on the unit sphere as densely as possible? We can reformulate this as finding the maximal weighted independent set in a certain graph on infinitely many vertices. The theta number is a graph parameter which upper bounds this hard to compute independence number. We generalize the weighted theta number to infinite graphs to find new upper bounds for the density of multiple-size spherical cap packings. For finite graphs one can view the theta number as the first step in a hierarchy of optimization problems whose optima converge to the
independence number; we generalize this hierarchy to infinite graphs and discuss its convergence. Based on joint work with Fernando Mário de Oliveira Filho and Frank Vallentin.
Diego Mirandola (UL, CWI) - Asymptotic lower bound on the dimension of product codes
This is a work done during my Master Thesis, under the supervision of Professor Gilles Zémor. Given a linear code C in K^n of dimension k, one can consider the code C-hat generated by the componentwise products of its codewords. The dimension k-hat of the product code is larger than k, and in general it happens that, repeating this powering operation, we quickly get the full space K^n. We give an asymptotic lower bound on k-hat, depending on k,n and on the dual distance of C, and we give a sketch of the proof. Also, we remark that this bound is tight, i.e. we have a family of codes which attain it.
René Pannekoek (Universiteit Leiden) - Explicit unbounded ranks of Jacobians in towers of function fields
This is joint work with Doug Ulmer and six other co-authors. For each prime power q and each odd prime r not dividing q, we define a curve C of genus r-1 over F_q(t). We give explicit generators for a subgroup of (Jac(C))(K), where K runs through a tower of extensions of F_q(t), and prove that the rank of this subgroup grows linearly with [K:F_q(t)]. We subsequently prove that the subgroup is actually of finite index.
Rachel Newton (UL) - Explicit local reciprocity for tame extensions
I will give a formula which computes the local reciprocity map for a tame abelian extension of local fields of degree n, without assuming the presence of a primitive nth root of unity in the base field. I will explain how I derived this formula via a definition of local reciprocity in terms of cyclic algebras and the Hasse invariant. I will end by discussing the difficulties which arise when the field extension is wildly ramified. This talk should be accessible to anyone who has encountered extensions of local fields.
Jongyook Park (TiU) - On distance-regular graphs with a small number of vertices compared to the valency
In this talk we study distance-regular graphs with a small number of vertices compared to the valency. We show that for a given $\alpha>2$, there are finitely many distance-regular graphs $\Gamma$ with valency $k$, diameter $D\geq3$ and $v$ vertices satisfying $v\leq\alpha k$ unless ($D=3$ and $\Gamma$ is imprimitive) or ($D=4$ and $\Gamma$ is antipodal and bipartite). As a consequence of this result, we also show that there are finitely many distance-regular graphs with valency $k\geq3$, diameter $D\geq3$ and $c_2\geq\varepsilon k$ for a given $0<\varepsilon <1$ unless ($D=3$ and $\Gamma$ is imprimitive) or ($D=4$ and $\Gamma$ is antipodal and bipartite).
Kieran Roberts (TiU and TU Eindhoven) - Extremal elements of Lie algebras
Lie theory is an active and important field of mathematics whose applications are widespread throughout mathematics and physics. In particular, the study of Lie algebras is a significant part of this theory. The structure of Lie algebras was first studied by Wilhelm Killing and in 1888 he classified the simple Lie algebras over the complex numbers. These simple Lie algebras give rise to a whole new family of Lie algebras called Chevalley algebras. In this talk we explain how the Chevalley algebras can be characterised by special elements, called extremal elements, and its associated geometry.