Clément Canonne

Phone

347-403-6758

e-mail

<initial><last name>@cs.columbia.edu (OpenPGP key)

Mailing address

910 Columbus Avenue — #1D
New York, NY 10025

Office Hours

Monday, 9:30—11:30 (CSB 516)

I am a Theory PhD student in the Computer Science department of Columbia University, where my adviser is Prof. Rocco Servedio. Prior to that, I received a M.Sc. in Computer Science from the Parisian Master of Research in Computer Science, in Paris, and an engineering degree from one of France's "Grand Schools", the Ecole Centrale Paris.
Here is a link to my résumé (updated 11/03/2016).

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

• Fall 2016: CSORW 4231-2 — 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)

Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.) ([ECCC TR16-168])

E. Blais, C. Canonne, and T. Gur

Manuscript, 2016.

Featured in Oded Goldreich's Choices.

Testing Bayesian Networks

C. Canonne, I. Diakonikolas, D. Kane, and A. Stewart

Manuscript, 2016.

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

Manuscript, 2016.

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 (To appear).

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

Proceedings of the 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.

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

ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

Testing probability distributions using conditional samples ([ECCC TR12-155], [arXiv], [slides])

C. Canonne, D. Ron, and R. Servedio.

SIAM Journal on Computing (SICOMP), 44(3), 2015.

Featured in Oded Goldreich's Choices.

I like this word. Miscellaneous.

• The Rise and Fall of Boolean Functions [slides]
Presentation given at 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 TR15-063], [bib])
Survey, 2015. (most recent version)
• 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).
• Testing probability distributions using conditional samples [slides]
Presentation given at Columbia University, NYU Poly, and MIT, 2013.

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.