BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Value of Errors in Proofs - Avi Wigderson (IAS\, Princeton)
DTSTART:20240415T130000Z
DTEND:20240415T140000Z
UID:TALK224968@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:Recently\, a group of theoretical computer scientists posted a
  \npaper on the Arxiv with the strange-looking title "MIP* = RE"\, surpris
 ing and impacting not only complexity theory but also some areas of math \
 nand physics. Specifically\,  it resolved\, in the negative\, the "Connes'
  \nembedding conjecture" in the area of von-Neumann algebras\, and the \n"
 Tsirelson problem" in quantum information theory. It further connects Turi
 ng's seminal 1936 paper which defined algorithms to Einstein's 1935 paper 
 with Podolsky and Rosen which challenged quantum mechanics. You can find t
 he \npaper here https://arxiv.org/abs/2001.04383\n\nAs it happens\, both a
 cronyms MIP* and RE represent proof systems\, of a \nvery different nature
 . To explain them\, we'll take a meandering jurney \nthrough the classical
  and modern definitions of proof. I hope to explain \nhow the methodology 
 of computational complexity theory\, especially \nmodeling and classificat
 ion (of both problems and proofs) by algorithmic \nefficiency\, naturally 
 leads to the genaration of new such notions and \nresults (and more acrony
 ms\, like NP). A special focus will be on notions \nof proof which allow i
 nteraction\, randomness\, and errors\, and their \nsurprising power and ma
 gical properties.
LOCATION:Computer Laboratory\, William Gates Building\, LT1
END:VEVENT
END:VCALENDAR