Talk abstracts, DIAMANT Symposium, May 31/June 1 2012, Hotel Veldenbos, Nunspeet

Invited speakers (55 min talks):

Friedrich Eisenbrand (EPFL Lausanne) - Diameter of Polyhedra: Limits of abstraction and new upper bounds

One of the most prominent mysteries in convex geometry is the question whether the diameter of a polyhedron can be bounded by a polynomial function in the dimension and its number of facets. The best known upper bound is n^{ log d +1}  (Kalai & Kleitman 1992) while no super linear lower bound is known. In this talk I will explain that this quasi polynomial bound also holds for very simple abstractions of polyhedral graphs and I will provide a super linear lower bound in this abstract setting. I will also discuss new upper bounds on the diameter of polyhedra that are polynomial in the maximum sub-determinant of the defining matrix and the dimension. This new bound improves upon a previous result of Dyer and Frieze in the setting of polyhedra defined by totally unimodular matrices.
The talk is based on joint work with N. Bonifas, N. Hähnle, S. Razborov, M. Niemeier and  T. Rothvoss

Christiane Frougny (LIAFA, Paris) - On parallel addition in non-standard numeration systems

It is well known that addition in a classical numeration system has a worst time linear complexity, which is too low to design an efficient arithmetical unit. In 1961, Avizienis gave a parallel algorithm for addition in base 10 with digit set {-6, -5, ..., 5, 6} where the carry does not propagate. This gives a constant time complexity (in parallel). In the language of symbolic dynamics, such an addition is a sliding block code function, also called a local function. The Avizienis technique is mainly used to fasten multiplication and division algorithms.
In this talk we consider positional numeration systems where the base is an algebraic number beta, |beta|>1. We show that when all the algebraic conjugates of beta have a modulus different from 1, it is possible to find a finite alphabet of signed digits on which parallel addition is possible. This algorithm is a generalisation of the one of Avizienis. The algorithm is quite simple, but the obtained alphabet can be larger than necessary. We then give lower bounds on the minimal cardinality of an alphabet of contiguous integer digits allowing parallel addition. We then develop several cases on which the lower bound is attained: negative base, complex base -1+i, quadratic Pisot units. We also consider the case of a rational base a/b, b >1.
Work in collaboration with Edita Pelantová and Milena Svobodová (CTU, Prague)

Sam Payne (Yale, MPIM Bonn) - Tropical Brill-Noether theory

Classical Brill-Noether theory studies the geometry of special divisors on smooth projective curves, with special attention to the existence of special divisors on the general curve of genus g. One fundamental result of the theory, called the Brill-Noether Theorem and due to Griffiths and Harris, says that a general curve of genus g has a divisor of degree d that moves in a linear system of dimension r if and only if g is at least (r+1)(g-d+r). The original proof uses a degeneration to a rational curve with g nodes, plus a very subtle transversality argument for certain associated Schubert cycles. I will present a new ``tropical" approach to the Brill-Noether Theorem, using the combinatorics of chip-firing, and the theory of ranks of divisors on graphs, introduced by Baker and Norine. This talk is based on joint work with Filip Cools, Jan Draisma, and Elina Robeva.

Ronald de Wolf (CWI and University of Amsterdam) - Exponential Lower Bounds for Polytopes in Combinatorial Optimization

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. Joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary.

Contributed speakers (25 min talks):

Jop Briët (CWI) - Violating the Shannon capacity of a graph with quantum entanglement

The Shannon capacity of a graph G gives the maximum asymptotic rate at which messages can be sent with zero probability of error through a noisy communication channel with confusability graph G. This extensively studied graph parameter disregards the fact that on atomic scales, Nature behaves in line with quantum mechanics. Entanglement, arguably the most counterintuitive feature of the theory, turns out to be a useful resource for communication across noisy channels. In this talk I present a large and simple family of graphs for which the entangled capacity exceeds the Shannon capacity, adding to two isolated examples found earlier by Leung, Mancinska, Matthews, Ozols and Roy (2012), which show that entanglement can increase the asymptotic rate of zero-error communication over discrete memoryless channels. Joint work with Harry Buhrman and Dion Gijswijt.

Rob Eggermont (TU/e) - Degree bounds on tree models

Tree models are families of probability distributions used in modelling the evolution of a number of extant species from a common ancestor. One method to describe these models is to view a family as a set in the m-fold tensor product of a vectorspace V, where m is the number of extant species, and to try to find polynomial equations that determine its Zariski closure. One important question in this area of research is the following: Can we bound the degree of the equations we need independently of the number of extant species? In this talk, I will tell a bit more about these models and will explain how to prove the existence a bound on the degree of the needed equations by constructing an infinite limit of models of a specific form.

Jinbi Jin (Universiteit Leiden) - Multiplication by n on elliptic curves over arbitrary rings

For elliptic curves over fields given by a Weierstrass equation, it is one of the basic facts that the multiplication by n map can be given in terms of so-called division polynomials. In this talk, I will generalise this fact for elliptic curves given by a Weierstrass equation over arbitrary rings.

Janne Kool (Universiteit Utrecht) - Dynamics measured in a non-Archimedean field

The study of dynamical systems using measure-theoretic methods has shown to be extremely useful. In almost all results real or complex valued measures are used. However, there exists theories in which measures take values in other fields, in particular non-Archimedean fields. In this talk I will discuss natural translation of several notions, e.g., probability measures, isomorphic transformations, conjugate transformations, from classical dynamical systems to a non-Archimedean setting.

Rutger Kuyper (RU Nijmegen) - Logic & Probability

We will study a non-classical logic in which the universal quantifier is interpreted as 'for almost all x' (in the sense of 'with high probability') instead of 'for all x', but in which the existential quantifier retains its classical interpretation. This way, one can decide if a formula holds in some model by amassing enough (but a finite amount of) evidence, unlike in classical logic. The mathematical theory behind our logic diverges from the classical theory at various points and the proofs require different techniques. In this talk, I will introduce the logic and give an overview of the results we have obtained so far.

Shoumin Liu (TU Eindhoven) - Brauer algebras of non-simply laced type

It is a very classical knowledge that simple groups of Lie types of non-simply laced type can be attained from the simply laced ones by considering nontrivial automorphisms of their Dynkin diagrams. This idea was extended to a more general theory called admissible partition by Muhlherr in the 1990s. In this talk, we apply these ideas to the Brauer algebras of simply-laced type which are studied by
Cohen, Frenk and Wales and dene Brauer algebras of non-simply laced type by generators and relations. We prove that they are free, compute their ranks and find bases by use of combinatorial data on their root systems; we also prove their cellularity in the sense of Graham and Lehrer.

Guus Regts (CWI) - On limits of edge coloring models

In this talk we consider limits of edge coloring models. Any linear function h on the polynomial ring in n variables is called an n-color edge coloring model. The partition function of h is a graph parameter p(F,h) (where F is a graph). We call a sequence (h^i) of edge coloring models convergent if for every simple graph F, the sequence(p(F_i,h)) has a limit. In this talk I will describe limit objects for convergent sequences of real edge coloring models; they can be seen as elements of the (real) polynomial ring in infinitely many variables. This work is closely related to and inspired by the recent theory of graph limits developed by Lovász, Szegedy and others. I will also say something about this relation. This talk is based on joint work with A. Schrijver.

Andrea Siviero (Universiteit Leiden) - Equidistribution of the Galois module structure of ring of integers with given local behavior

Let K be a number field and let G be a finite abelian group. A couple of years ago Melanie Wood studied the probabilities of various splitting types of a fixed prime in a random G-extension of K. When the number fields are counted by conductor, she proved that the probabilities are as predicted by a heuristic and independent at distinct primes. In the same period Adebisi Agboola studied the asymptotic behavior of the number of tamely ramified G-extensions of K with ring of integers of fixed realizable class as a Galois module, proving that an equidistribution result exists when the extensions are counted by conductor. One natural question is: are the two distributions of Wood and Agboola independent? In this talk I will briefly give the answer to this question when we require a totally split local behavior.

Piotr Zwiernik - Graphical Gaussian models and their groups

Let G be an undirected graph with n nodes. Let S(G) be the set of all (n x n) real symmetric, positive definite matrices with zeros corresponding to non-edges of G.  We describe the stabilizer of S(G) in GL_n(R) of the model, in the natural action of GL_n(R) on symmetric matrices. The main motivation for this work is in statistics, where S(G) is identified with the graphical Gaussian model on G. Our results have important consequences for the study of the maximum likelihood inference for this model class. This is a joint work with Jan Draisma and Sonja Kuhnt.



Mathematics cluster DIAMANT

Upcoming events

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.