Monday, February 8, 2016
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
One of my favourite open questions is the following:
"Is Sato's Grassmannian Noetherian up to symmetry?"
At first sight, this question seems quite remote from discrete mathematics, but I hope to convince you otherwise. Along the way,
I will review recent developments in infinite-dimensional commutative algebra, in which combinatorial notions such as well-partial-orders play a fundamental role.
Colloquium - 16:00
Abstract:
We consider the fundamental problem of exploring an undirected and initially unknown graph by an agent with little memory. The vertices of the graph are unlabeled, and the edges incident to a vertex have locally distinct labels. In this setting, it is known that Θ(log n) bits of memory are necessary and sufficient to explore any graph with at
most n vertices. We show that this memory requirement can be decreased significantly by making a part of the memory distributable in the form of pebbles. A pebble is a device that can be dropped to mark a vertex and can be collected when the agent returns to the vertex. We show that for an agent O(log log n) distinguishable pebbles and bits of memory are sufficient to explore any bounded-degree graph with at most
n vertices. We match this result with a lower bound exhibiting that for any agent with sub-logarithmic memory, Ω(log log n) distinguishable pebbles are necessary for exploration.