BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Subcubic certificates for CFL reachability - Dmitry Chistikov\, Un
 iversity of Warwick
DTSTART:20221104T140000Z
DTEND:20221104T150000Z
UID:TALK184937@talks.cam.ac.uk
CONTACT:Jamie Vicary
DESCRIPTION:The context-free language (CFL) reachability problem on graphs
  (as well as\na closely related problem of language emptiness for pushdown
  automata) is\na core problem for interprocedural program analysis and mod
 el checking.\nIt can be solved in cubic time but\, despite years of effort
 s\, there is no\ntruly sub-cubic algorithm known for it.\n\nWe study the r
 elated certification task: given a problem instance\, are\nthere small and
  efficiently checkable certificates for the existence and\nfor the non-exi
 stence of a path? We show that there exist succinct\ncertificates\, of qua
 dratic size\, which can be checked in subcubic (matrix\nmultiplication) ti
 me.\n\nIn this talk\, I will introduce CFL reachability and standard algor
 ithms for it\nand discuss our certification results. I will also discuss t
 he question of\nwhether faster algorithms for CFL reachability could lead 
 to faster algorithms\nfor other combinatorial problems such as SAT (a "fin
 e-grained complexity"\nquestion).\n\nJoint work with Rupak Majumdar and Ph
 ilipp Schepper.
LOCATION:SS03
END:VEVENT
END:VCALENDAR