How to prove - hopefully - that polynomial time is not choiceless

Add to your list(s) Download to your calendar using vCal

• Benedikt Pago
• Friday 13 October 2023, 14:00-15:00
• SS03, Computer Laboratory.

If you have a question about this talk, please contact Anuj Dawar.

A long-standing open problem in finite model theory is the question whether there exists a logic that captures polynomial time. Put differently, this question asks for a symmetry-invariant computation model which decides precisely the polynomial time computable properties of finite structures. Most logics that have been proposed were subsequently separated from polynomial time. One important candidate for which such a separation has not been achieved (in more than twenty years) is the logic Choiceless Polynomial Time (CPT). 
In this talk, I will introduce CPT along with techniques from finite model theory and group theory which can be used to reason about its limitations. Results obtained with these methods provide evidence that CPT may not be powerful enough to capture all of PTIME . I also suggest a concrete route towards separating CPT from PTIME via symmetric circuit lower bounds.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• SS03, Computer Laboratory
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• tcw57’s list
• yk373's list

Note that ex-directory lists are not shown.