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
when asking questions), and uploaded to the SMRI YouTube Channel
https://www.youtube.com/c/SydneyMathematicalResearchInstituteSMRI