I know that prof. Appel is a really smart guy from reading his books on optimizing compilers - so I'm going to risk looking like an idiot here, especially because I don't have time to carefully read the paper.. but maybe someone can help me out here.
so he says that a buyer cannot determine that a CDO has been maliciously packed with bad assets because this is equivalent to finding the densest subgraph. Is there a reason why an approximate solution to the dense subgraph
problem could not allow one to conclude that a CDO was more likely to have been stuffed with garbage?
clearly if the problem is truly like encryption as Appel says then an approximate solution is worthless (an approximate encryption key would still give you garbage)
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).
I see - thanks for the info. I didn't know the background of the author or recognize the reference. I'm going to read this one over much more carefully.
One issue is the vocabulary of the word equivilent.
With poloynomial time problem reductions (which is what is usually used with showig a problem is NP complete, though I too haven't read the paper) equivilent just means something like "an exact solution in A translates to an exact solution in B." Unfortunatly, in general, an approxmimate solution to A doens't translate to an approxmiate solution to B.
Note: This part is me really guessing so please don't take it at face falue.
If I had to guess, I'd say that this is like densest subgraph in the sense that:
The mortgages are the nodes.
High correlation --> Edge connections.
So there might be a straightforward translation of approxmiate solutions. Like I said, just a guess.
I'd guess that even if you can't solve the problem exactly you could find a tractable probabilistic solution that works x% of the time and traders spend their time finding such solutions. The real problem is that for the (1-x)% of the time when it doesn't work it wrecks major havoc.
Like all theorems in complexity, this one is saying something that is true only for the most general problems. Reality is, most problems found in the real world are just special cases of the truly generic NP-hard problems. That is why we can find algorithms for many of them (deterministic or stochastic). So, basically the theorem doesn't really say much about the financial problem, unless you believe that the modeling here is 100% correct - which, considering any non-trivial financial scenario, is not.
so he says that a buyer cannot determine that a CDO has been maliciously packed with bad assets because this is equivalent to finding the densest subgraph. Is there a reason why an approximate solution to the dense subgraph problem could not allow one to conclude that a CDO was more likely to have been stuffed with garbage?
clearly if the problem is truly like encryption as Appel says then an approximate solution is worthless (an approximate encryption key would still give you garbage)