Event Detail

Fri Nov 2, 2012
60 Evans Hall, 4:10–6 PM
Logic Colloquium
Joseph Mileti (Grinnell College)
Computable Combinatorics

We survey the history and some recent results analyzing theorems about trees, graph colorings, and other combinatorial structures from the viewpoint of computable mathematics. By analyzing the complexity of solutions to computable instances of these problems, we discover some striking connections across different theorems and gain insight into the techniques required in every possible proof.