Some computational and combinatorial applications of simplicial topology

ABSTRACT: The well-known Sperner Lemma occupies a central role in the
field of simplicial topology. It is known to be essentially equivalent to
the famous Brouwer fixed-point theorem, to the no-retraction theorem and
other fundamental facts in topology. Over the years Sperner's Lemma has
found applications in many other fields including various parts of
computer science, mathematical economics and combinatorics. In this talk I
will recall Sperner's Lemma and show in detail a recent application in
distributed computing (from a joint work with Y. Afek, U. Feige, E. Gafni
and B. Sudakov). If time permits, I will also speak briefly about two
other beautiful applications of simplicial topology - Kahn, Saks and
Sturtevant's work on evasiveness of graph properties and Aharoni and
Haxell's work on matchings in hypergraphs. No background in topology is
required to follow this talk.

BIO: Nati Linial is a Professor of computer science at the Hebrew
University, Jerusalem and a frequent visitor to MSR. His work has had
major influence on several areas of computer Science and combinatorics; In
particular he initiated the study of cover times for random walks and
(with Miki Ben Or) of the influence of variables on Boolean functions. See
http://www.cs.huji.ac.il/~nati/