1/26ECOM Spotlight Series: Julian Schloeder
ECOM Spotlight Series: Julian SchloederThursday, January 26th, 202311:00 AM - 12:30 PMStorrs CampusZoomContact Information: firstname.lastname@example.org More
Coffee HourThursday, January 26th, 202301:00 PM - 02:00 PMStorrs CampusStern Lounge
1/27Logic Colloquium: Josh Grochow (Colorado)
Logic Colloquium: Josh Grochow (Colorado)Friday, January 27th, 202302:00 PM - 03:30 PMStorrs CampusZoom
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 Information: email@example.com More