BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:How to prove - hopefully - that polynomial time is not choiceless 
 - Benedikt Pago
DTSTART:20231013T130000Z
DTEND:20231013T140000Z
UID:TALK206965@talks.cam.ac.uk
CONTACT:Anuj Dawar
DESCRIPTION:A long-standing open problem in finite model theory is the que
 stion whether there exists a logic that captures polynomial time. Put diff
 erently\, this question asks for a symmetry-invariant computation model wh
 ich decides precisely the polynomial time computable properties of finite 
 structures. Most logics that have been proposed were subsequently separate
 d from polynomial time. One important candidate for which such a separatio
 n has not been achieved (in more than twenty years) is the logic Choiceles
 s 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 a
 lso suggest a concrete route towards separating CPT from PTIME via symmetr
 ic circuit lower bounds.
LOCATION:SS03\, Computer Laboratory
END:VEVENT
END:VCALENDAR