Events & News
CS Colloquium
| Category | Lecture |
| Date | Thursday, November 6, 2014 |
| Time | 11:00 am |
| Concludes | 12:15 pm |
| Location | Gould-Simpson 906 |
| Details | Please join us for coffee and light refreshments at 11am in Gould-Simpson 906. Faculty Host: Larry Peterson |
| Speaker | Lev Reyzin |
| Title | Assistant Professor |
| Affiliation | Dept of Mathematics, Statistics, & Computer Science, University of Illinois |
Statistical Algorithms and the Planted Clique Problem
In this talk, I will present a framework for analyzing a wide range of computational problems over distributions. I will define a class of algorithms called statistical algorithms, which captures most natural methods used in theory and practice. I will discuss how this lens can help us analyze many well-known problems and give lower bounds on the complexity of any statistical algorithm for them. These include a nearly optimal lower bound for detecting planted clique distributions, a problem that arises in many areas, including community detection in social networks, public key encryption in cryptography, and theoretical computer science. This work begins to explain this problem's hardness and also sheds light on how we can hope to make progress in devising new optimization algorithms. I will also illustrate connections to machine learning theory.
This work is joint with Vitaly Feldman, Elena Grigorescu, Santosh Vempala, and Ying Xiao.
Biography
Lev Reyzin is a tenure-track Assistant Professor in the MCS group at UIC's mathematics department. His research spans the theory and practice of machine learning. Previously, Lev was a Simons Postdoctoral Fellow at Georgia Tech, and before that, an NSF CI-Fellow at Yahoo! Research, where he tackled problems in computational advertising. Lev received his Ph.D. from Yale under Dana Angluin and his undergraduate degree from Princeton. His work has earned awards at ICML, COLT, and AISTATS, as well as several national fellowships.