[Discrete-math-seminar] Colloquium: Tuesday, September 5, 2017: Lev Reyzin, 12:45pm RE 106

Hemanshu Kaul kaul at iit.edu
Mon Sep 4 19:42:04 CDT 2017

We will have a talk tomorrow by Prof. Lev Reyzin of CS, UIC, on Statistical
Algorithms for Combinatorial and Optimization problems that should be of
interest to most folks in these mailing lists. The talk is on Tuesday,
September 5th, at 106, RE, at 12:45pm. See below for details.


*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
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.

Hemanshu Kaul
Associate Professor of Applied Mathematics
Co-Director, Graduate Program on Decision Sciences (CDSOR)
Illinois Institute of Technology
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://math.iit.edu/pipermail/discrete-math-seminar/attachments/20170904/0ae74389/attachment.html>

More information about the Discrete-math-seminar mailing list