Is there a reason why an approximate solution to the dense subgraph problem could not allow I haven't read the paper either ;] (just skimmed bibliography to ge

Is there a reason why an approximate solution to the dense subgraph problem could not allow I haven't read the paper either ;] (just skimmed bibliography to get a sense, as I usually do first) but Arora (one of the authors) is an expert on probabilistic approximations, and they do cite 2001 paper by Feige which is standard ref. on approximations to dense subgraph. Also, what they reduce their model to is a "planted" hidden clique variant of dense subgraph, a problem which is hard "on average" and not only in worst case (propety used in crypto protocols also).