NOVEMBER 20, 2015

Speaker: Jennifer Chubb, University of San Francisco
Title: Distance functions on computable graphs

Abstract: A graph is computable if its edge relation is algorithmically decidable. Given two vertices on a connected computable graph, we can ask, "what is the length of the shortest path between them." Of course for a connected graph we can always algorithmically find a path and determine its length, but the question of finding a shortest path is harder and is not in general computable for infinite graphs.

In considering the question of the computational complexity of the distance function on computable graphs, a number of interesting issues arise. We'll begin by looking at effective properties of the family of functions that, like the distance function, have a computable, decreasing approximation. Next, we'll study the specific example of the distance function of a computable graph. We'll see that functions that are computably approximable from above can be coded, in rather a strong sense, into such a distance function, and so this question is, in a sense, as hard as it could possibly be.

This work is joint will Wesley Calvert and Russell Miller.

Time: Friday, November 20, 2015, 3:30-4:20 p.m.

Place: Exploratory Hall, room 4106

Refreshments will be served at 3:00 p.m.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
Tel. 703-993-1460, Fax. 703-993-1491