ARC Colloquium: Vitaly Feldman, IBM Almaden Research Center, San Jose, CA.

Event Details
  • Date/Time:
    • Wednesday May 1, 2013 - Thursday May 2, 2013
      1:00 pm - 12:59 pm
  • Location: Klaus 1116
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:



Summary Sentence: No summary sentence submitted.

Full Summary: No summary paragraph submitted.

Title: Statistical Algorithms and a Lower Bound for Detecting Planted Cliques


We introduce a framework for proving lower bounds on computational problems over distributions, based on a 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. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalizes the statistical query model in learning theory.

Our main application is a nearly optimal lower bound on the complexity of any statistical algorithm 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 these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

Joint work with Elena Grigorescu, Lev Reyzin, Santosh Vempala and Ying Xiao


Additional Information

In Campus Calendar

College of Computing, School of Computer Science, ARC

Invited Audience
No audiences were selected.
No categories were selected.
No keywords were submitted.
  • Created By: Elizabeth Ndongi
  • Workflow Status: Published
  • Created On: Apr 11, 2013 - 6:53am
  • Last Updated: Oct 7, 2016 - 10:03pm