Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Lev Reyzin:

TR12-064 | 10th May 2012
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh Vempala, Ying Xiao

Statistical Algorithms and a Lower Bound for Planted Clique

Revisions: 2

We develop a framework for proving lower bounds on computational problems over distributions, including optimization and unsupervised learning. Our framework is based on defining a restricted class of algorithms, called statistical algorithms, that instead of accessing samples from the input distribution can only obtain an estimate of the expectation ... more >>>

ISSN 1433-8092 | Imprint