A Conditional Least-Squares Hardness Reduction from Exact-Size Small-Set Expansion
Abstract
We give a conditional hardness result for the sparse least square regression problem (conjecture 27 in https://jmlr.csail.mit.edu/papers/volume22/20-661/20-661.pdf)
