Tue, 19 Oct 2010

14:30 - 15:30
L3

Sorting under Partial Information and Partial Order Entropy

Jean Cardinal
(Universite Libre de Bruxelles)
Abstract

We revisit the problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time sorting algorithm achieving this bound up to a constant factor. They established a crucial link between the entropy of the input partial order and the information-theoretic lower bound. However, their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it unpractical. We develop efficient algorithms for sorting under partial information, derived from approximation and exact algorithms for computing the partial order entropy.

This is joint work with S. Fiorini, G. Joret, R. Jungers, and I. Munro.

Tue, 12 Oct 2010

14:30 - 15:30
L3

A couple of easy cases for counting Euler tours

Mary Cryan
(Edinburgh)
Abstract

The problem of checking existence for an Euler tour of a graph is trivial (are all vertex degrees even?). The problem of counting (or even approximate counting) Euler tours seems to be very difficult. I will describe two simple classes of graphs where the problem can be

solved exactly in polynomial time. And also talk about the many many classes of graphs where no positive results are known.

Mon, 25 Oct 2010

12:00 - 13:00
L3

On the gravity duals of N=2 superconformal field theories

Ron Reid-Edwards
(Oxford)
Abstract
In 2009 Gaiotto and Maldacena demonstrated that the challenge of finding gravitational descriptions of N=2 superconformal field theories could, under certain circumstances, be reduced to a simple two-dimensional electrostatics problem. In this talk I will review their work and discuss recent progress in finding and interpreting such solutions in string and M-theory.
Thu, 21 Oct 2010

16:00 - 17:00
L3

Almost prime points on homogeneous varieties

Dr A Gorodnik
(Bristol)
Abstract

Given a polynomial function f defined on a variety X,

we consider two questions, which are non-commutative analogues

of the Prime Number Theorem and the Linnik Theorem:

- how often the values of f(x) at integral points in X are almost prime?

- can one effectively solve the congruence equation f(x)=b (mod q)

with f(x) being almost prime?

We discuss a solution to these questions when X is a homogeneous

variety (e.g, a quadratic surface).

Mon, 15 Nov 2010

15:45 - 16:45
L3

$L^p$ cohomology and pinching

Pierre Pansu
(Orsay)
Abstract

We prove that no Riemannian manifold quasiisometric to

complex hyperbolic plane can have a better curvature pinching. The proof

uses cup-products in $L^p$-cohomology.

Mon, 01 Nov 2010

15:45 - 16:45
L3

Analogues of Euler characteristic

Tom Leinster
(Glasgow)
Abstract

There is a close but underexploited analogy between the Euler characteristic

of a topological space and the cardinality of a set. I will give a quite

general definition of the "magnitude" of a mathematical structure, framed

categorically. From this single definition can be derived many

cardinality-like invariants (some old, some new): the Euler characteristic

of a manifold or orbifold, the Euler characteristic of a category, the

magnitude of a metric space, the Euler characteristic of a Koszul algebra,

and others. A conjecture states that this purely categorical definition

also produces the classical invariants of integral geometry: volume, surface

area, perimeter, .... No specialist knowledge will be assumed.

Subscribe to L3