“And who, shall I say, is calling?”

Picture of me.

Clément Canonne

(Page probably under construction. Far from finished.)

Contact information

Phone
347-403-6758
e-mail
<initial><last name>@cs.columbia.edu (OpenPGP key)
Mailing address

Stanford University (Computer Science Department)
Gates 496, 353 Serra Mall
Stanford, CA 94305

About me

I am a postdoc in the Stanford Theory Group. I recently 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 10/25/2017).

Research Interests

My main areas of study are Property Testing, Learning Theory, and, more generally, randomized algorithms. However, I do also have an interest in online and approximation Algorithms, as well as stochastic processes.

Teaching

Papers

Testing Conditional Independence of Discrete Distributions
C. Canonne, I. Diakonikolas, D. Kane, and A. Stewart
Manuscript.
Fourier-Based Testing for Families of Distributions ([ECCC TR17-075], [slides])
C. Canonne, I. Diakonikolas, and A. Stewart
Manuscript.
Improved Bounds for Testing Forbidden Order Patterns
O. Ben-Eliezer and C. Canonne
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. (To appear)
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism ([ECCC TR16-105])
E. Blais, C. Canonne, T. Eden, A. Levi, and D. Ron
29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018. (To appear)
Generalized Uniformity Testing ([slides])
T. Batu and C. Canonne
58th Annual Symposium on Foundations of Computer Science (FOCS), 2017. (To appear)
Fifty Shades of Adaptivity (in Property Testing): An Adaptivity Hierarchy Theorem for Property Testing ([ECCC TR17-029, arXiv:1702.05678], [slides])
C. Canonne and T. Gur
Computational Complexity Conference (CCC), 2017.
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.) ([ECCC TR16-168], [slides])
E. Blais, C. Canonne, and T. Gur
Computational Complexity Conference (CCC), 2017.
Featured in Oded Goldreich's Choices.
Testing Bayesian Networks
C. Canonne, I. Diakonikolas, D. Kane, and A. Stewart
30th Annual Conference on Learning Theory (COLT), 2017.
Testing k-Monotonicity: the Rise and Fall of Boolean Functions ([ECCC TR16-136], [slides])
C. Canonne, E. Grigorescu, S. Guo, A. Kumar, and K. Wimmer
8th Innovations in Theoretical Computer Science (ITCS), 2017.
Sampling Correctors ([slides])
C. Canonne, T. Gouleakis, and R. Rubinfeld
7th Innovations in Theoretical Computer Science (ITCS), 2016.
Are Few Bins Enough: Testing Histogram Distributions ([ECCC TR15-160], [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 TR14-144], [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 TR14-156], [slides])
J. Acharya, C. Canonne, and G. Kamath
19th International Workshop on Randomization and Computation (RANDOM), 2015.
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 TR14-153], [slides])
C. Canonne, V. Guruswami, R. Meka, and M. Sudan
6th Innovations in Theoretical Computer Science (ITCS), 2015.
IEEE Transactions on Information Theory, 63(10), 2017.
Testing probability distributions underlying aggregated data ([ECCC TR14-021], [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 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.
Testing probability distributions using conditional samples ([ECCC TR12-155], [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

Property Testing and Probability Distributions: New Techniques, New Models, and New Goals [slides, source, thesis commons]
Ph.D. Thesis, 2017

Miscellaneous

I like this word. Miscellaneous. I am one of the organizers of TCS+, an online seminar series in theoretical computer science. I also am part of the Property Testing Review blog, and also sometimes contribute to the MIT Theory of Computation Student Blog as a non-affiliated invader. Occasionally, I run.