Clément Canonne
(Page probably under construction. Far from finished.)
Contact information
 Phone
 3474036758
 <initial><last name>@cs.columbia.edu (OpenPGP key)
 Mailing address

650 Harry Road
IBM Almaden, B2403
San Jose, CA 95120
About me
I am currently a postdoc at IBM Research Almaden, and will be joining the School of Computer Science of the University of Sydney as a Lecturer in January 2021. Prior to that, I was a postdoc in the Stanford Theory Group. 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 Ecole Centrale Paris.
Here is a link to my résumé (updated 01/25/2020).Research Interests
My main areas of study are property testing (with a focus on distribution testing), learning theory, and, more generally, randomized algorithms and the theory of machine learning. Additionally, I am interested in online and approximation algorithms, as well as stochastic processes.
Papers
Unless explicitly specified otherwise, authorships are in alphabetical order, as is customary in theoretical computer science.
 Robust quantum minimum finding with an application to hypothesis selection ([arXiv:2003.11777])
 Y. Quek, C. Canonne, and P. Rebentrost (Contribution order)
 Manuscript, 2020.
 Random Restrictions of HighDimensional Distributions and Uniformity Testing with Subcube Conditioning ([arXiv:1911.07357, ECCC TR19165], [slides])
 C. Canonne, X. Chen, G. Kamath, A. Levi, and E. Waingarten
 Manuscript, 2019.
 Private Identity Testing for HighDimensional Distributions
 C. Canonne, G. Kamath, A. McMillan, J. Ullman, and L. Zakynthinou
 Manuscript, 2019.
 Presented at the 2019 Workshop on Theory and Practice of Differential Privacy (TPDP 2019), and accepted to the Privacy in Machine Learning (PriML) workshop of NeurIPS 2019.
 Testing Data Binnings ([arXiv:2004.12893, ECCC TR20062])
 C. Canonne and K. Wimmer
 24th International Conference on Randomization and Computation (RANDOM), 2020. (To appear)
 Distributed Signal Detection under Communication Constraints
 J. Acharya, C. Canonne, and H. Tyagi
 33rd Annual Conference on Learning Theory (COLT), 2020. (To appear)
 Domain Compression and its Application to RandomnessOptimal Distributed GoodnessofFit ([ECCC TR19098], [slides])
 J. Acharya, C. Canonne, Y. Han, Z. Sun, and H. Tyagi
 33rd Annual Conference on Learning Theory (COLT), 2020. (To appear)
 Learning from satisfying assignments under continuous distributions
 C. Canonne, A. De, and R. Servedio
 31st ACMSIAM Symposium on Discrete Algorithms (SODA), 2020.
 Finding monotone patterns in sublinear time [arXiv:1910.01749, ECCC TR19134]
 O. BenEliezer, C. Canonne, S. Letzter, and E. Waingarten
 60th Annual Symposium on Foundations of Computer Science (FOCS), 2019.
 Featured in Oded Goldreich's Choices.
 Inference under Information Constraints II: Communication Constraints and Shared Randomness ([slides])
 J. Acharya, C. Canonne, and H. Tyagi
 2019 International Conference on Machine Learning (ICML), 2019. (Long oral.)
 See also the preprint Distributed Simulation and Distributed Inference ([arXiv:1804:06952,ECCC TR18079]), a preliminary but somewhat extended version of this work.
 Inference under Information Constraints I: Lower Bounds from ChiSquare Contraction ([video], [slides])
 J. Acharya, C. Canonne, and H. Tyagi
 32nd Annual Conference on Learning Theory (COLT), 2019.
 See also the video of the talk given by H. Tyagi on the Shannon Channel.
 The Structure of Optimal Private Tests for Simple Hypotheses
 C. Canonne, G. Kamath, A. McMillan, A. Smith, and J. Ullman
 51st ACM Symposium on Theory of Computing (STOC), 2019.
 Test without Trust: Optimal Locally Private Distribution Testing
 J. Acharya, C. Canonne, C. Freitag, and H. Tyagi
 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), 2019.
 Presented at the 2018 Workshop on Theory and Practice of Differential Privacy (TPDP 2018).
 Testing for Families of Distributions via the Fourier Transform ([arXiv:1706:05738, [ECCC TR17075], [slides])
 C. Canonne, I. Diakonikolas, and A. Stewart
 Advances in Neural Information Processing Systems 31 (NeurIPS), 2018.
 Testing Conditional Independence of Discrete Distributions ([slides])
 C. Canonne, I. Diakonikolas, D. Kane, and A. Stewart
 50th ACM Symposium on Theory of Computing (STOC), 2018.
 Improved Bounds for Testing Forbidden Order Patterns
 O. BenEliezer and C. Canonne
 29th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2018.
 Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism ([ECCC TR16105])
 E. Blais, C. Canonne, T. Eden, A. Levi, and D. Ron
 ACM Transactions on Computation Theory (TOCT), 11(4), 2019.
 Conference version in 29th Annual ACMSIAM Symposium on Discrete Algorithms (SODA), 2018.
 Generalized Uniformity Testing ([slides], [video])
 T. Batu and C. Canonne
 58th Annual Symposium on Foundations of Computer Science (FOCS), 2017.
 Distribution Testing Lower Bounds via Reductions from Communication Complexity ([ECCC TR16168], [slides])
 E. Blais, C. Canonne, and T. Gur
 ACM Transactions on Computation Theory (TOCT), 11(2), 2019.
 Conference version in Computational Complexity Conference (CCC), 2017.
 Featured in Oded Goldreich's Choices.
 An Adaptivity Hierarchy Theorem for Property Testing ([ECCC TR17029, arXiv:1702.05678], [slides])
 C. Canonne and T. Gur
 computational complexity, 27(4), 2018.
 Conference version in Computational Complexity Conference (CCC), 2017.
 Testing Bayesian Networks
 C. Canonne, I. Diakonikolas, D. Kane, and A. Stewart
 IEEE Transactions on Information Theory, 66(5), 2020.
 Conference version in 30th Annual Conference on Learning Theory (COLT), 2017.
 Testing kMonotonicity: the Rise and Fall of Boolean Functions ([ECCC TR16136], [slides])
 C. Canonne, E. Grigorescu, S. Guo, A. Kumar, and K. Wimmer
 Theory of Computing, 15(1), 2019.
 Conference version in 8th Innovations in Theoretical Computer Science (ITCS), 2017.
 Sampling Correctors ([arXiv:1504.06544], [slides])
 C. Canonne, T. Gouleakis, and R. Rubinfeld
 SIAM Journal on Computing (SICOMP), 47(4), 2018.
 Conference version in 7th Innovations in Theoretical Computer Science (ITCS), 2016.
 Are Few Bins Enough: Testing Histogram Distributions ([ECCC TR15160], [slides])
 C. Canonne
 35th ACM Symposium on Principles of Database Systems (PODS), 2016.
 Testing Shape Restrictions of Discrete Distributions
 C. Canonne, I. Diakonikolas, T. Gouleakis, and R. Rubinfeld
 33rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2016.
 Invited to the Theory of Computing Systems Special Issue for STACS 2016.
 Featured in the MIT Theory of Computation Student Blog.
 Learning circuits with few negations ([ECCC TR14144], [slides])
 E. Blais, C. Canonne, I. Oliveira, R. Servedio, and L.Y. Tan
 19th International Workshop on Randomization and Computation (RANDOM), 2015.
 A Chasm Between Identity and Equivalence Testing with Conditional Queries ([ECCC TR14156], [slides])
 J. Acharya, C. Canonne, and G. Kamath
 19th International Workshop on Randomization and Computation (RANDOM), 2015.
 Theory of Computing, 14(19), 2018.
 Featured in Oded Goldreich's Choices and Sublinear.info.
 Big Data on the Rise: Testing monotonicity of distributions ([slides])
 C. Canonne
 42nd International Conference on Automata, Languages and Programming (ICALP), 2015.
 Adaptive Estimation in Weighted Group Testing
 J. Acharya, C. Canonne, and G. Kamath
 2015 IEEE International Symposium on Information Theory (ISIT 2015).
 Communication with Imperfectly Shared Randomness ([ECCC TR14153], [slides])
 C. Canonne, V. Guruswami, R. Meka, and M. Sudan
 IEEE Transactions on Information Theory, 63(10), 2017.
 Conference version in 6th Innovations in Theoretical Computer Science (ITCS), 2015.
 Testing probability distributions underlying aggregated data ([ECCC TR14021], [slides])
 C. Canonne and R. Rubinfeld
 41st International Conference on Automata, Languages and Programming (ICALP), 2014.
 Testing equivalence between distributions using conditional samples ([slides])
 C. Canonne, D. Ron, and R. Servedio
 25th ACMSIAM Symposium on Discrete Algorithms (SODA), 2014.
 Testing probability distributions using conditional samples ([ECCC TR12155], [arXiv:1211.2664], [slides])
 C. Canonne, D. Ron, and R. Servedio.
 SIAM Journal on Computing (SICOMP), 44(3), 2015.
 Featured in Oded Goldreich's Choices.
Thesis
Service
 Program Committee member:
 ITCS 2020, FOCS 2020, SODA 2021
 Coorganizer of Foundations of Data Science Virtual Talk Series, an online seminar series on the theory of data science.
 Coorganizer of TCS+, an online seminar series in theoretical computer science.
 Coeditor of the Property Testing Review.
 Workshop on "A TCS Quiver" [slides]
 Coorganized with Gautam Kamath at FOCS'19.
 Workshop on "Frontiers in Distribution Testing" [slides,video]
 Coorganized with Gautam Kamath at FOCS'17.
 Workshop on "(Some) Orthogonal Polynomials and their Applications to TCS" [slides,video]
 Coorganized with Gautam Kamath at FOCS'16.
Teaching
 Spring 2017: COMS E6232 — Analysis of Algorithms, II (Teaching Assistant)
 Fall 2016: CSORW 42312 — Analysis of Algorithms, I (Teaching Assistant)
 Spring 2015: COMS E6232 — Analysis of Algorithms, II (Teaching Assistant)
 Fall 2014: COMS 4252 — Introduction to Computational Learning Theory (Teaching Assistant)
 Spring 2014: COMS 6998 — Sublinear Time Algorithms in Learning and Property Testing (Teaching Assistant)
 Fall 2013: COMS 4252 — Introduction to Computational Learning Theory (Teaching Assistant)
 Spring 2013: COMS E6232 — Analysis of Algorithms, II (Teaching Assistant)
 Fall 2012: COMS 4252 — Introduction to Computational Learning Theory (Teaching Assistant)
Miscellaneous
I like this word. Miscellaneous.
 A short note on learning discrete distributions
 Technical thingy, 2020.
 A short note on Poisson tail bounds
 Technical thingy, 2017.
 The Rise and Fall of Boolean Functions [slides]
 Presentation given at the University of Waterloo on May 16, 2016.
 Testing Classes of Distributions: General Approaches to Particular Problems [slides]
 Presentation given at Columbia University (October 2) and LIX (December 17), 2015.
 Learning circuits with few negations [slides]
 Presentation given at LIAFA on June 23, 2015.
 A Survey on Distribution Testing: Your Data is Big. But is it Blue? ([ECCC TR15063], [bib])
 Survey, 2015. (most recent version (2017/06))
 To appear in Theory of Computing as a “Graduate Survey.”
 A short note on Assouad and Le Cam's lemmata
 Technical thingy, 2015.
 Communication with Imperfect Shared Randomness [slides]
 Presentation given at Columbia University (November 7), IBM T.J. Watson Research Center (November 19), 2014 (long version of the ITCS'15 talk).
 Testing probability distributions with more oracles [slides]
 Presentation given at Columbia University on February 7, 2014 (long version of the ICALP'14 talk).
 Dompter les Distributions de Probabilité Géantes [FR]
 Translation of Taming Big Probability Distributions, by Ronitt Rubinfeld (DOI:10.1145/2331042.2331052).