Statistical algorithms and a lower bound for detecting planted cliques

• DOI: 10.1145/2488608.2488692
• Publication Date: 2013-05-28T16:35:41Z
• Authors: Vitaly Feldman; Elena Grigorescu; Lev Reyzin; Santosh Vempala; Ying Xiao
• Keywords: Clique

We introduce a framework for proving lower bounds on computational problems over distributions, based class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited obtaining an estimate expectation any given function sample drawn randomly from distribution, rather than directly accessing samples. Most natural interest in theory and practice, e.g., moments-based methods, local search, standard iterative methods convex optimization, MCMC simulated annealing, are or have counterparts. Our inspired by generalize query model learning [34]. main application nearly optimal bound complexity algorithm detecting planted bipartite clique distributions (or dense subgraph distributions) when has size O(n1/2-δ) constant δ > 0. Variants these been assumed be hard prove hardness other cryptographic applications. provide concrete evidence hardness, thus supporting assumptions.