This mathematics paper (with this FAQ ) has attracted some attention from bloggers. Briefly the paper starts with a model in which sellers construct collateralized debt obligations (or CDOs) from many different asset types (and with each asset type appearing in many different CDOs). If the seller knows some of the asset types are lemons (eg are worse risks than they appear) then the seller can create lemon CDOs by assigning them more than their fair share of the lemon asset types. The paper claims to show (using the conjectured intractability of the densest subgraph problem) that this nonrandom assignment is much easier for the seller to do than for the buyer to detect.
I have no reason to doubt the mathematics in this paper but I do doubt its real world significance. The larger risk with such CDOs from the buyer's point of view is that the CDOs will be overpriced across the board not that they will purchase CDOs from a malevolently constructed fraction of lemons. This is what went wrong with the mortgage backed CDOs whose loss of value contributed so much to the recent crisis. The pricing models for these CDOs overvalued them by incorporating a number of overly optimistic assumptions. When this became apparent their prices collapsed. As far as I know the scenario in paper is purely hypothetical.
I don't see much point in worrying about hypothetical problems before fixing readily apparent real problems. And I don't think this particular hypothetical problem would actually be all that difficult to solve. It seems to me that it should be possible to devise a transparent verifiable randomization procedure if that should be felt to be important.
My opinion is this problem will prove to be largely moot going forward. These CDO products grew explosively because they could be sold for more than they were worth. Presumably potential buyers have wised up and this will no longer be possible. In which case I don't think these products have much reason for existing and will largely disappear.