Thesis Information
Title: Property Testing and Probability Distributions: New Techniques, New Models, and New Goals
Adviser: Rocco Servedio
Institution: Columbia University
Graduation Date: October 2019
Contact Information
Email Candidate
Candidate Website
SIGACT Membership No.: 8042312
Candidate Bio:
I am currently a Goldstine fellow at IBM Research. Before that, I spent two years as a Motwani postdoctoral fellow in the Stanford Theory Group. Even before, 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.
Paper 1:
"Testing probability distributions using conditional samples," C. Canonne, D. Ron, and R. Servedio; SICOMP, 2015 (conference version in SODA, 2014)
Link to PDFPaper 2:
"Distribution testing lower bounds via reductions from communication complexity," E. Blais, C. Canonne, and T. Gur; TOCT, 2019 (conference version in CCC, 2017)
Link to PDFPaper 3:
"Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction," J. Acharya, C. Canonne, and H. Tyagi; COLT, 2019
Link to PDFKeywords: computational learning, property testing, distribution testing, theoretical machine learning