[Discrete-math-seminar] Reminder: Department Colloquium Tuesday, September 5, 2017: Lev Reyzin, 12:45pm RE 106
Robert Ellis
ellisr at iit.edu
Tue Sep 5 08:13:19 CDT 2017
Dear all,
A reminder of today's talk. Note the non-standard day (Tuesday), time
(12:45pm), and room (RE 106).
Please join the Department of Applied Mathematics for our colloquium this
coming Monday at 1:50pm in RE 104 (formerly E1 104).
*Time:* Tuesday, September 5, 12:45pm-1:45pm
*Location:* RE 106 (Rettaliata Engineering Center)
Coffee and cookies afterward in RE 112 until 2:30pm
*Speaker:* Lev Reyzin, Assistant Professor - Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago
*Title:* Statistical Algorithms and Planted Cliques
*Abstract*
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 combinatorial and optimization 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. 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. Time permitting, I
will also discuss algorithms and potential lower bounds for planted
partition problems. Random linear systems and computational learning theory
will also make an appearance.
This talk mainly covers work joint with Vitaly Feldman, Elena Grigorescu,
Santosh Vempala, and Ying Xiao and also touches on work with Sam Cole and
Shmuel Friedland.
--
Robert B. Ellis, PhD
Assoc. Prof., IIT Applied Mathematics
10 W 32nd St, E1 208, Chicago, IL 60637
ellisr at iit.edu
http://math.iit.edu/~rellis
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/discrete-math-seminar/attachments/20170905/a90c1665/attachment.html>
More information about the Discrete-math-seminar
mailing list