[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium July 18.

[Ita Brunke <i.brunke@fu-berlin.de>]

Dear all,

our next and last Monday's Lecture and Colloquium will take place on July 18 at 14:15 & 16:00 at FU Berlin.

You are all cordially invited.

Location:

Room 005 - Ground Floor
Freie Universität Berlin
Takustr. 9
14195 Berlin

Time: Monday, July 18 - 14:15

Lecture: Herman Haverkort (Universität Bonn)

Title: Space-filling curves: properties, applications and challenges

Abstract:

A space-filling curve is a continuous, surjective map from [0,1] to a d-dimensional unit volume (for example, a cube or a simplex). Space-filling curves are usually constructed following a recursive tessellation of the unit volume that gives the curve useful structural properties. The most prominent of these properties is that the curve tends to preserve locality: points that are close to each other along the curve are (usually) close to each other in d-dimensional space and (usually) vice versa. This can be exploited to speed up algorithms, in practice and sometimes even in theory, by processing or storing data points in order along the curve. In this lecture I will show how space-filling curves can be described, how they get their useful properties, and I will show examples of their applications. This brings us to the question what would be the optimal space-filling curves for these applications. We will encounter a number of open questions on tessellations in 2D and 3D and on how to measure the quality of a space-filling curve.

Coffee & Tea Break :

Room 134 - 1st Floor


Time: Monday, July 18 - 16:00 s.t.

Colloquium: Andrea Jiménez (Universidad de Varparaíso, Chile)

Title: Groundstates of the Ising Model on antiferromagnetic triangulations

Abstract:

We discuss a dual version of a problem about perfect matchings in cubic graphs posed by Lovasz and Plummer. The dual version is formulated as follows "Every triangulation of an orientable surface has exponentially many groundstates'', where groundstates are the states at the lowest energy in the antiferromagnetic Ising Model.

According to physicists, this dual formulation holds. In this talk, I show a counterexample to the dual formulation, a method to count groundstates which gives a better bound (for the original problem) on the class of Klee-graphs, the complexity of the related problems and, if time allows, some open problems.

This is joint work with Marcos Kiwi and Martin Loebl.