• Reception to follow in MLH 3. Join us to chat with the speaker and other attendees.

Speaker: Rocco Servedio, Ph.D., Professor and former Chair of Computer Science, Columbia University

Abstract
Sparsity is a desirable property in many data analysis scenarios. A large body of work in the field of property testing --- most prominently, the long and successful research effort aimed at "junta testing" --- has studied the problem of testing whether an unknown function has a sparse representation. But algorithms for these kinds of problems generally require query access to the unknown function that is being tested, and often perform poorly in the presence of noise. This is a potential problem, because in many natural data analysis scenarios we may not have query access to the underlying function and the data that we are given may be noisy. Are there natural sparsity testing scenarios in which highly efficient testers can be given, which only require random samples of the input data (rather than queries) and moreover succeed in the presence of noise? This talk will survey some recent and ongoing works that give a positive answer to this question.Based on a combination of joint works with Yiqiao Bao (U. Penn), Xue Chen (University of Science and Technology of China), Anindya De (U. Penn), Shivam Nadimpalli (MIT), Chenyang Sun (Columbia), and Nathan White (U. Penn).

Bio
Rocco Servedio is a professor and former chair of the Department of Computer Science at Columbia University. He was an NSF postdoc at Harvard University, where he received his PhD studying under Leslie Valiant, before joining Columbia. He is a recipient of the Alfred P. Sloan Research Fellowship, the NSF CAREER Award, and the Columbia University Presidential Teaching Award, and has received best paper or best student paper awards from the STOC, FOCS, SODA, CCC and COLT conferences. Rocco’s research interests lie in theoretical computer science, particularly computational complexity theory (concrete complexity, pseudorandomness, and analysis of Boolean functions), computational learning theory (learnability of Boolean functions and probability distributions), and sublinear time algorithms (property testing).