Variable Selection is Hard.

Dean P. Foster, Howard J. Karloff, Justin Thaler

Browse the full COLT paper archive.