SMS scnews item created by Hannah Bryant at Wed 6 Apr 2022 1656
Type: Seminar
Modified: Wed 6 Apr 2022 1658; Wed 6 Apr 2022 1658
Distribution: World
Expiry: 12 Apr 2022
Calendar1: 12 Apr 2022 1500-1600
CalTitle1: SMRI ’What is ...?’ Seminar: Canonne ’What is deterministic amplification?’
Auth: hannahb@w63dq1n2.mcs.usyd.edu.au (hbry8683) in SMS-SAML

# SMRI ’What is ...?’ Seminar: Canonne -- What is deterministic amplification?

SMRI ’What is ...?’ Seminar
’What is deterministic amplification?’
Clement Canonne
(University of Sydney)

Tuesday 12 April 3:00-4:00pm (AEST) Quad S227 & Online via zoom
Register for online attendance here:
https://uni-sydney.zoom.us/meeting/register/tZIuceigrj0jH9NU84QQJI6y0WMGZ51PGl1Z

Abstract: Suppose we want to solve a given task (say, a decision problem) and have a
randomised algorithm for it which is correct; but only with some non-trivial
probability, for instance .51.  We would like to "amplify" this probability of success
to an arbitrarily small amount, as close to 1 as possible: how to do this? And, more
importantly, how to do this using as little extra randomness as possible?

I will first discuss why one would want to do this, then how to achieve it naively, and
-- quite surprisingly -- how we can do much better than this naive approach using
expander graphs.

Biography: Clement Canonne is a Lecturer in the School of Computer Science of the
University of Sydney; he obtained his Ph.D.  in 2017 from Columbia University, before
joining Stanford as a Motwani Postdoctoral Fellow, then IBM Research as a Goldstine
Postdoctoral Fellow.  His main areas of research are distribution testing (and, broadly
speaking, property testing) and learning theory; focusing, in particular, on
understanding the computational aspects of learning and statistical inference subject to
various resource or information constraints.

Note This seminar will be recorded, including participant questions (participants only