Dr Clement Canonne
Senior Lecturer
School of Computer Science
Dr Clément Canonne is a Senior Lecturer in the School of Computer Science, where he does research in theoretical computer science. His main research interests lie in property testing, learning theory, and, more generally, randomised algorithms and the theory of machine learning.
Prior to joining the University of Sydney, Clément was a Goldstine postdoctoral fellow at IBM Research Almaden, and a Motwani fellow at Stanford University. He obtained his Ph.D. from Columbia University in 2017.
Collecting, analysing, and processing large volumes of data, often high-dimensional, has become a centerpiece of modern computer science, machine learning, and industry at large. The time and memory constraints associated with these amounts of information present unprecedented challenges, as classical algorithms and statistical techniques are no longer sufficient to analyse the data. Further, new and even more stringent constraints have emerged, such as critical privacy concerns, or the physical limitations of battery- and communication-limited devices. Dr. Clément Canonne's research focuses on formalising those challenges, and developing sound theoretical foundations to address them.
"My research lies at the intersection of algorithms, information theory, statistics, and computational learning theory, and asks questions of the following flavour. When trying to perform a specific task on very large datasets, do we need exact answers or are approximate ones good enough? Must we store the data itself, or is some concise representation sufficient for our applications? Can interactivity or randomisation help reducing the computational load? What are the tradeoffs, if any, that one can achieve or must incur between privacy, speed, and accuracy?
"Overall, the goal is to analyse the fundamental and practical questions that emerge from the massive amounts of data available. I strive to develop new tools and techniques to analyse the many settings that arise, focusing not only on the purely statistical constraints at play, but also on the new computational and societal aspects that are now at the front and center of data science."
Publications
Journals
- Acharya, J., Canonne, C., Singh, A., Tyagi, H. (2023). Optimal Rates for Nonparametric Density Estimation under Communication Constraints. IEEE Transactions on Information Theory. [More Information]
- Acharya, J., Canonne, C., Liu, Y., Sun, Z., Tyagi, H. (2022). Interactive Inference under Information Constraints. IEEE Transactions on Information Theory, 68(1), 502-516. [More Information]
- Canonne, C., Kamath, G., Steinke, T. (2022). THE DISCRETE GAUSSIAN FOR DIFFERENTIAL PRIVACY. The Journal of Privacy and Confidentiality, 12(1). [More Information]
Conferences
- Canonne, C., Lyu, C. (2022). Uniformity Testing in the Shuffle Model: Simpler, Better, Faster. SIAM Symposium on Simplicity in Algorithms, Online: Society for Industrial and Applied Mathematics (SIAM).
- Acharya, J., Canonne, C., liu, Y., Sun, Z., Tyagi, H. (2021). Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition. 35th Conference on Neural Information Processing Systems (NeurIPS 2021), Sydney: Neural Information Processing Systems (NIPS).
- Canonne, C., Wimmer, K. (2021). Identity Testing Under Label Mismatch. 32nd International Symposium on Algorithms and Computation, ISAAC 2021, Germany: Schloss Dagstuhl--Leibniz-Zentrum fur Informatik. [More Information]
2023
- Acharya, J., Canonne, C., Singh, A., Tyagi, H. (2023). Optimal Rates for Nonparametric Density Estimation under Communication Constraints. IEEE Transactions on Information Theory. [More Information]
2022
- Acharya, J., Canonne, C., Liu, Y., Sun, Z., Tyagi, H. (2022). Interactive Inference under Information Constraints. IEEE Transactions on Information Theory, 68(1), 502-516. [More Information]
- Canonne, C., Kamath, G., Steinke, T. (2022). THE DISCRETE GAUSSIAN FOR DIFFERENTIAL PRIVACY. The Journal of Privacy and Confidentiality, 12(1). [More Information]
- Canonne, C. (2022). Topics and Techniques in Distribution Testing. Foundations and Trends in Communications and Information Theory, 19(6), 1032-1198. [More Information]
2021
- Acharya, J., Canonne, C., liu, Y., Sun, Z., Tyagi, H. (2021). Distributed Estimation with Multiple Samples per User: Sharp Rates and Phase Transition. 35th Conference on Neural Information Processing Systems (NeurIPS 2021), Sydney: Neural Information Processing Systems (NIPS).
- Canonne, C., Wimmer, K. (2021). Identity Testing Under Label Mismatch. 32nd International Symposium on Algorithms and Computation, ISAAC 2021, Germany: Schloss Dagstuhl--Leibniz-Zentrum fur Informatik. [More Information]
- Acharya, J., Canonne, C., Freitag, C., Sun, Z., Tyagi, H. (2021). Inference under information constraints III: local privacy constraints. IEEE Journal on Selected Areas in Information Theory, 2(1), 253-267. [More Information]
2020
- Acharya, J., Canonne, C., Tyagi, H. (2020). Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction. IEEE Transactions on Information Theory, 66(12), 7835-7855. [More Information]
- Acharya, J., Canonne, C., Tyagi, H. (2020). Inference under Information Constraints II: Communication Constraints and Shared Randomness. IEEE Transactions on Information Theory, 66(12), 7856-7877. [More Information]
- Canonne, C., De, A., Servedio, R. (2020). Learning from satisfying assignments under continuous distributions. 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM).
2019
- Acharya, J., Canonne, C., Tyagi, H. (2019). Communication-constrained inference and the role of shared randomness. 36th International Conference on Machine Learning (ICML 2019), : SPIE.
- Blais, E., Canonne, C., Gur, T. (2019). Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory, 11(2), 6. [More Information]
- Ben-Eliezer, O., Canonne, C., Letzter, S., Waingarten, E. (2019). Finding monotone patterns in sublinear time. Annual Symposium on Foundations of Computer Science (FOCS 2019), Baltimore: Institute of Electrical and Electronics Engineers (IEEE). [More Information]
2018
- Acharya, J., Canonne, C., Kamath, G. (2018). A chasm between identity and equivalence testing with conditional queries. Theory of Computing, 14, 19. [More Information]
- Canonne, C., Gur, T. (2018). An adaptivity hierarchy theorem for property testing. Computational Complexity, 27(4), 671-716. [More Information]
- Ben-Eliezer, O., Canonne, C. (2018). Improved bounds for testing forbidden order patterns. The Twenty-Ninth Annual ACM/SIAM Symposium on Discrete Algorithms (SODA 2018), USA: Society for Industrial and Applied Mathematics (SIAM). [More Information]
2017
- Canonne, C., Gur, T. (2017). An adaptivity hierarchy theorem for property testing. 32nd Computational Complexity Conference (CCC 2017), Riga: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
- Canonne, C., Guruswami, V., Meka, R., Sudan, M. (2017). Communication with Imperfectly Shared Randomness. IEEE Transactions on Information Theory, 63(10), 6799-6818. [More Information]
- Blais, E., Canonne, C., Gur, T. (2017). Distribution testing lower bounds via reductions from communication complexity. 32nd Computational Complexity Conference (CCC 2017), Riga: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. [More Information]
2015
- Canonne, C., Ron, D., Servedio, R. (2015). Testing probability distributions using conditional samples. SIAM Journal on Computing, 44(3), 540-616. [More Information]
Selected Grants
2022
- Efficient Algorithmic Primitives for Private Distributed Statistical Inference, Canonne C, Google Asia Pacific Pte. Ltd/Research Support