Type: Seminar

Modified: Wed 6 Apr 2022 1658; Wed 6 Apr 2022 1658

Distribution: World

Expiry: 12 Apr 2022

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 ’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