[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR
 
 
Tuesday, May 7, 2013
3:00 p.m.
Ryerson 251
 
Elena Grigorescu
Purdue University
web.ics.purdue.edu/~egrigore/
 
Title: Lower bounds for statistical algorithms
 
Abstract: We introduce a framework for proving lower bounds on computational problems over distributions, based on de fining a restricted class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples.  Our definition and techniques are inspired by and generalize the statistical query model in learning theory. For well-known problems over distributions, we give lower bounds on the complexity of any statistical algorithm. These include an exponential lower bounds for moment maximization in R^n, and a nearly optimal lower bound for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n^{1/2-delta}_) for any constant _ delta> 0. Variants of the latter have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence supporting these assumptions.
 
Joint work with: Vitaly Feldman, Lev Reyzin, Santosh Vempala, Ying Xiao.
 
Host: Prof. Alexander Razborov
 
*Refreshments will be served prior to the talk at 2:30 in Ryerson 255*
 
 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130502/8e2ee5cf/attachment.htm