Computer Science/Discrete Mathematics Seminar I | |

Topic: | Choiceless Polynomial Time |

Speaker: | Ben Rossman |

Affiliation: | University of Toronto |

Date: | Monday, October 14 |

Time/Room: | 11:00am - 12:00pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/1017-BenRossman |

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 choiceless algorithm cannot freely select 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 give an overview of results in the choiceless model and discuss the intriguing open question: Does every graph property that is decidable by a poly-time Turing machine admit a choiceless poly-time algorithm?