On Tuesday, January 17, Seth Harris of Drew University will be speaking about "On-Line Algorithms and Reverse Mathematics." The talk will be from 2:30-3:30 PM in Kemeny 004.

Abstract:

Consider a two-player game (played by Alice and Bob) in which Alice asks a sequence <a_0, ..., a_k> and Bob responds with a sequence <b_0, ..., b_k> with no knowledge of Alice's future requests. A problem P is solvable by an *on-line algorithm* if Bob has a winning strategy in this game, where Bob wins the game if (\bar{a}, \bar{b}) constitutes a solution to P. For example, if we take P to be a graph coloring problem, Alice plays by adding a new vertex and edges connecting it to previous vertices; Bob chooses a color for that vertex. The graph is *on-line colorable* if Bob has a winning strategy in this game.

Given a problem P, the corresponding *sequential problem* SeqP asserts the existence of an infinite sequence of solutions to P.

We will show that the reverse-mathematical strength of SeqP is directly related to the on-line solvability of P, and we will exactly characterize which sequential problems are solvable in RCA_0, WKL_0, and ACA_0. This is joint work with François Dorais.