Sparse Linear Regression Is Easy on Random Supports.

Gautam Chandrasekaran, Raghu Meka, Konstantinos Stavropoulos

Browse the full STOC paper archive.