Thursday


11:0011:25

arrival and coffee

11:2511:30

welcome

Ronald de Wolf

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

11:3012:25

We solve a 20year old problem posed by M. Yannakakis and prove that
there exists no polynomialsize 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 oneway quantum
communication protocols and semidefinite programming reformulations of
LPs. Joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta,
Hans Raj Tiwary. 
Jop Briët

Violating the Shannon capacity of a graph with quantum entanglement

12:3012:55

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 zeroerror communication over discrete memoryless channels. Joint work with Harry Buhrman and Dion Gijswijt.

13:0014:45

lunch

Rob Eggermont

Degree bounds on tree models 
14:4515:10

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
mfold 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.

Janne Kool

Dynamics measured in a nonArchimedean field 
15:1515:40

The study of dynamical systems using measuretheoretic 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 nonArchimedean 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 nonArchimedean
setting. 
15:4516:15

tea 
Jinbi Jin

Multiplication by n on elliptic curves over arbitrary rings 
16:1516:40

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 socalled division polynomials. In this talk, I will generalise
this fact for elliptic curves given by a Weierstrass equation over
arbitrary rings.

Christiane Frougny

On parallel addition in nonstandard numeration systems 
16:4517:40 
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)

17:4519.00

drinks

19:00

dinner 


Friday


Friedrich Eisenbrand

Diameter of Polyhedra: Limits of abstraction and new upper bounds 
9:009:55

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 subdeterminant 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. 
Rutger Kuyper

Logic & Probability

10:0010:25

We will study a nonclassical 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.

10:3011:00

coffee

Shoumin Liu

Brauer algebras of nonsimply laced type 
11:0011:25

It is a very classical knowledge that simple groups of Lie types of
nonsimply 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 simplylaced type which are studied by
Cohen, Frenk and Wales and dene Brauer algebras of nonsimply 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

On limits of edge coloring models 
11:3011:50 
In this talk we consider limits of edge coloring models. Any linear
function h on the polynomial ring in n variables is called an ncolor
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.

12:0013:00

lunch

Andrea Siviero

Equidistribution of the Galois module structure of ring of integers with given local behavior 
13:0013:25

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 Gextension 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 Gextensions 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 
13:3013:55

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 nonedges 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.

14:0014:20 
tea

Sam Payne

Tropical BrillNoether theory 
14:2015:15

Classical BrillNoether 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 BrillNoether 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)(gd+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 BrillNoether Theorem, using the combinatorics of
chipfiring, 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. 