BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Randomised computation - Daria Dicu\, Sidney Sussex College
DTSTART:20151125T190000Z
DTEND:20151125T194000Z
UID:TALK62534@talks.cam.ac.uk
CONTACT:Matthew Ireland
DESCRIPTION:Randomised algorithms are the simplest and fastest known solut
 ion to many decision problems. We reason about randomised algorithms using
  the concept of probabilistic Turing machines\, which are a variant of non
 deterministic Turing machines that have probabilistic transition choice.\n
 \nThis talk is aimed as a discussion around the various complexity classes
  associated with randomised computation (BPP\, RP\, ZPP). I shall start by
  presenting these classes\, alongside known relationships between them and
  complexity classes studied in the Part IB course (P\, NP).\n\nWe will the
 n see how randomised algorithms provide much more efficient solutions than
  deterministic ones by looking at the Schwartz-Zippel lemma applied to Pol
 ynomial Identity Testing\, which gives a polynomial time Monte Carlo algor
 ithm\, as opposed to its deterministic counterpart\, which is exponential.
 \n\nIn conclusion\, I shall discuss the open problem of P = BPP and the us
 age of pseudorandom number generators to deterministically simulate random
 ised algorithms.
LOCATION:Club Room\, Churchill College
END:VEVENT
END:VCALENDAR