Title: Choiceless Polynomial Time
Presented By: Benjamin Rossman, University of Toronto

Abstract:
The "choiceless" computation model of Blass, Gurevich and Shelah (1999, 2002) is an algorithmic framework for computing isomorphism-invariant properties of unordered structures. Machines in this model have the power of parallel execution, but lack the ability to make arbitrary choices. For example, a choiceness algorithm cannot freely pick an arbitrary neighbor of a vertex in an unordered graph, but may execute a subroutine in parallel over all neighbors. In this talk, I will introduce the choiceless model and discuss the intriguing open question: Is every polynomial-time graph property computable by a choiceless polynomial-time algorithm?