University of Connecticut

Events Calendar

Logic Colloquium: Josh Grochow (Colorado)

Friday, January 27, 2023
2:00pm – 3:30pm

Storrs Campus
Zoom

Join us for a talk in the Logic Colloquium!

Josh Grochow (Colorado)

Polynomial-time axioms of choice and polynomial-time cardinality

Many versions of the Axiom of Choice (AC), though equivalent in ZF set theory, are inequivalent from the computational point of view. When we consider polynomial-time analogues of AC, many of these different versions can be shown to be equivalent to other more standard questions about the relationship between complexity classes. We will use some of these formulations of AC to motivate several complexity questions that might otherwise seem a bit bespoke and unrelated from one another.

Next, as many versions of AC are about cardinals, in the second half of the talk we introduce a polynomial-time version of cardinality, in the spirit of polynomial-time model theory. As this is a new theory, we will discuss some of the foundational properties of polynomial-time cardinality, some of which may be surprising when contrasted with their set-theoretic counterparts. The talk will contain many open questions, and the paper contains even more! Based on arXiv:2301.07123 [http://cs.CC].

https://logic.uconn.edu/calendar/

Contact:

logic@uconn.edu

UConn Logic Group Colloquium (primary), College of Liberal Arts and Sciences, Philosophy Department, UConn Master Calendar

#eventtitle
Control Panel