Clément Canonne

ARC DECRA Fellow
Senior Lecturer, School of Computer Science
The University of Sydney
email
 clement.canonne@sydney.edu.au
address
J12 — School of Computer Science Building
Room 426
The University of Sydney
NSW 2006 Australia


I am a Senior Lecturer in the School of Computer Science of the University of Sydney, in the Sydney Algorithms and Computing Theory (SACT) group. Prior to that, I was a postdoc first in the Stanford Theory Group, then at IBM Research Almaden. Even prior to that, I obtained my Ph.D. from the Computer Science department of Columbia University, where I was advised by Prof. Rocco Servedio. Long ago, in a distant land, I received a M.Sc. in Computer Science from the Parisian Master of Research in Computer Science, and an engineering degree from one of France's "Grand Schools," the École Centrale Paris.

My main areas of study are distribution testing (and, broadly speaking, property testing), learning theory, and, more generally, randomised algorithms and the theory of machine learning. One of my current focuses is on understanding the computational aspects of learning and statistical inference subject to various resource or information constraints. Another, not quite disjoint from the first, lies in reliable and rigorous approaches to data privacy, specifically differential privacy.

CV (PDF)» ORCID Google Scholar DBLP BlueSky Mastodon


News


Advising

Prospective Ph.D. students: If you are an undergrad/masters student with a strong background in algorithms and/or discrete mathematics interested (broadly) in the theoretical aspects of learning, randomised algorithms, or privacy, and are keen on spending 3-4 years in one of the world's best places to live, you can contact me, including your CV and a short paragraph of introduction. Please check my publications for some of my recent work, or my recent survey.

I also regularly supervise research projects (over Summer and Winter) for undergraduate students, as part of the Engineering Vacation Research Internship Program, and Honours students (18cp). If you are interested in either, please get in touch!

  • Ph.D. (current): Kenny Chen (co-advised with Julián Mestre)
  • Ph.D. (current): Abigail Gentle
  • Ph.D. (current): Joy (Qiping) Yang
  • MPhil (graduated): Yun Li

Selected Publications All Publications»

generated by bibbase.org
  Manuscripts (1)
Unified lower bounds for interactive high-dimensional estimation under information constraints. Jayadev Acharya; Clément L. Canonne; Ziteng Sun; and Himanshu Tyagi. 2021.
Unified lower bounds for interactive high-dimensional estimation under information constraints [link]Paper   link   bibtex   156 downloads  
  Conference Papers (10)
The Price of Tolerance in Distribution Testing. Clément L. Canonne; Ayush Jain; Gautam Kamath; and Jerry Li. In COLT, 2022. To appear.
The Price of Tolerance in Distribution Testing [link]Paper   link   bibtex   189 downloads  
Optimal Rates for Nonparametric Density Estimation under Communication Constraints. Jayadev Acharya; Clément L. Canonne; Aditya Vikram Singh; and Himanshu Tyagi. In NeurIPS, 2021.
Optimal Rates for Nonparametric Density Estimation under Communication Constraints [link]Paper   link   bibtex   110 downloads  
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. Clément L. Canonne; Xi Chen; Gautam Kamath; Amit Levi; and Erik Waingarten. In SODA, 2021.
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning [link]Paper   link   bibtex   155 downloads  
Private Identity Testing for High-Dimensional Distributions. Clément L. Canonne; Gautam Kamath; Audra McMillan; Jonathan Ullman; and Lydia Zakynthinou. In NeurIPS, 2020. Spotlight Presentation
Private Identity Testing for High-Dimensional Distributions [link]Paper   link   bibtex   108 downloads  
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit. Jayadev Acharya; Clément L. Canonne; Yanjun Han; Ziteng Sun; and Himanshu Tyagi. In COLT, 2020.
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit [link]Paper   link   bibtex   64 downloads  
The Discrete Gaussian for Differential Privacy. Clément L. Canonne; Gautam Kamath; and Thomas Steinke. In NeurIPS, 2020.
The Discrete Gaussian for Differential Privacy [link]Paper   link   bibtex   122 downloads  
Communication-Constrained Inference and the Role of Shared Randomness. Jayadev Acharya; Clément L. Canonne; and Himanshu Tyagi. In ICML, pages 30–39, 2019. Long oral
Communication-Constrained Inference and the Role of Shared Randomness [link]Paper   link   bibtex   68 downloads  
The structure of optimal private tests for simple hypotheses. Clément L. Canonne; Gautam Kamath; Audra McMillan; Adam D. Smith; and Jonathan Ullman. In STOC, 2019.
The structure of optimal private tests for simple hypotheses [link]Paper   link   bibtex   63 downloads  
Testing Conditional Independence of Discrete Distributions. Clément L. Canonne; Ilias Diakonikolas; Daniel M. Kane; and Alistair Stewart. In STOC, 2018.
Testing Conditional Independence of Discrete Distributions [link]Paper   link   bibtex   80 downloads  
Testing for Families of Distributions via the Fourier Transform. Clément L. Canonne; Ilias Diakonikolas; and Alistair Stewart. In NeurIPS, 2018.
Testing for Families of Distributions via the Fourier Transform [link]Paper   link   bibtex   66 downloads  
  Journal Papers (11)
Interactive Inference Under Information Constraints. Jayadev Acharya; Clément L. Canonne; Yuhan Liu; Ziteng Sun; and Himanshu Tyagi. IEEE Transactions on Information Theory, 68(1): 502–516. 2022.
Interactive Inference Under Information Constraints [link]Paper   doi   link   bibtex   72 downloads  
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction. Jayadev Acharya; Clément L. Canonne; and Himanshu Tyagi. IEEE Transactions on Information Theory, 66(12): 7835–7855. 2020.
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction [link]Paper   link   bibtex   72 downloads  
Inference Under Information Constraints II: Communication Constraints and Shared Randomness. Jayadev Acharya; Clément L. Canonne; and Himanshu Tyagi. IEEE Transactions on Information Theory, 66(12): 7856–7877. 2020.
Inference Under Information Constraints II: Communication Constraints and Shared Randomness [link]Paper   link   bibtex   45 downloads  
Inference Under Information Constraints III: Local Privacy Constraints. Jayadev Acharya; Clément L. Canonne; Cody Freitag; Ziteng Sun; and Himanshu Tyagi. IEEE Journal on Selected Areas in Information Theory. 2021.
Inference Under Information Constraints III: Local Privacy Constraints [link]Paper   link   bibtex   57 downloads  
Testing Bayesian Networks. Clément L. Canonne; Ilias Diakonikolas; Daniel M. Kane; and Alistair Stewart. IEEE Transactions on Information Theory, 66(5): 3132–3170. 2020.
Testing Bayesian Networks [link]Paper   link   bibtex   56 downloads  
Distribution Testing Lower Bounds via Reductions from Communication Complexity. Eric Blais; Clément L. Canonne; and Tom Gur. ACM Transactions on Computation Theory, 11(2): 6:1–6:37. 2019.
Distribution Testing Lower Bounds via Reductions from Communication Complexity [link]Paper   doi   link   bibtex   60 downloads  
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. Eric Blais; Clément L. Canonne; Talya Eden; Amit Levi; and Dana Ron. ACM Transactions on Computation Theory, 11(4): 24:1–24:33. 2019.
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism [link]Paper   doi   link   bibtex   63 downloads  
An Adaptivity Hierarchy Theorem for Property Testing. Clément L. Canonne; and Tom Gur. computational complexity, 27(4). 2018.
An Adaptivity Hierarchy Theorem for Property Testing [link]Paper   doi   link   bibtex   39 downloads  
Testing Shape Restrictions of Discrete Distributions. Clément L. Canonne; Ilias Diakonikolas; Themis Gouleakis; and Ronitt Rubinfeld. Theory of Computing Systems, 62(1): 4–62. 2018. Invited issue for STACS 2016.
Testing Shape Restrictions of Discrete Distributions [link]Paper   doi   link   bibtex   62 downloads  
Communication With Imperfectly Shared Randomness. Clément L. Canonne; Venkatesan Guruswami; Raghu Meka; and Madhu Sudan. IEEE Transactions on Information Theory, 63(10): 6799–6818. 2017.
Communication With Imperfectly Shared Randomness [link]Paper   link   bibtex   37 downloads  
Testing probability distributions using conditional samples. Clément L. Canonne; Dana Ron; and Rocco A. Servedio. SIAM Journal on Computing (SICOMP), 44(3). 2015.
Testing probability distributions using conditional samples [link]Paper   doi   link   bibtex   53 downloads  
  Books, survey, and thesis (3)
Topics and Techniques in Distribution Testing: A Biased but Representative Sample. Clément L. Canonne. Foundations and Trends® in Communications and Information Theory, 19(6): 1032-1198. 2022. website
Topics and Techniques in Distribution Testing: A Biased but Representative Sample [link]Paper   doi   link   bibtex   248 downloads  
A Survey on Distribution Testing: Your Data is Big. But is it Blue?. Clément L. Canonne. Theory of Computing, (9). 2020.
A Survey on Distribution Testing: Your Data is Big. But is it Blue? [link]Paper   doi   link   bibtex   453 downloads  
Property Testing and Probability Distributions: New Techniques, New Models, and New Goals. Clément L. Canonne. Ph.D. Thesis, Columbia University, 2017. slides, source, thesis commons
doi   link   bibtex   14 downloads  


Professional Service

Conference Committees

  • European Symposium on Algorithms (ESA): 2021 (Track A)
  • Symposium on Foundations of Computer Science (FOCS): 2020
  • International Colloquium on Automata, Languages and Programming (ICALP): 2023 (Track A)
  • Innovations in Theoretical Computer Science (ITCS): 2020
  • International Conference on Randomization and Computation (RANDOM): 2021, 2023
  • Symposium on Discrete Algorithms (SODA): 2021, 2023
  • Symposium on Simplicity in Algorithms (SOSA): 2024
Workshops, Tutorials, and Symposia Organizer