Computer Science Colloquium, 2005-2006

Eitan Bachmat
Department of Computer Science, Ben-Gurion University
March 8th, 2006

Causal sets and their applications

Spacetime (Lorentzian) geometry was introduced by Minkowski to mathematically model relativity theory. A spacetime manifold carries a partial order which is interpreted as the past-future causal relation. It also carries a natural volume form which allows us to sample the manifold.

Sampling a manifold leads to a random finite poset, we call such objects causal sets. These objects first appeared as part of a particular approach to quantum gravity championed by R. Sorkin.

We will explain how several natural processes such as airplane boarding, scheduling in disk drives, patience sorting, the PNG surface growth model and others are naturally understood in terms of causal sets.

As a sample application we will analyze the effectivness of airplane boarding strategies, a work which recently received a considerable amount of media attention.

Joint work with D. Berend, L.sapir, S. skiena and N. Stolyarov.


Shuly Wintner
Last modified: Fri Feb 10 11:57:50 IST 2006