Randomised computation

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

• Daria Dicu, Sidney Sussex College
• Wednesday 25 November 2015, 19:00-19:40
• Club Room, Churchill College.

If you have a question about this talk, please contact Matthew Ireland.

Room changed: club room

Randomised algorithms are the simplest and fastest known solution to many decision problems. We reason about randomised algorithms using the concept of probabilistic Turing machines, which are a variant of nondeterministic Turing machines that have probabilistic transition choice.

This 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).

We will then see how randomised algorithms provide much more efficient solutions than deterministic ones by looking at the Schwartz-Zippel lemma applied to Polynomial Identity Testing, which gives a polynomial time Monte Carlo algorithm, as opposed to its deterministic counterpart, which is exponential.

In conclusion, I shall discuss the open problem of P = BPP and the usage of pseudorandom number generators to deterministically simulate randomised algorithms.

This talk is part of the Churchill CompSci Talks series.

This talk is included in these lists:

• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Churchill CompSci Talks
• Club Room, Churchill College
• Interested Talks
• Trust & Technology Initiative - interesting events
• bld31
• computer science
• ndk22's list
• ob366-ai4er
• rp587
• se393's list

Note that ex-directory lists are not shown.