2 problems

The statistical-computational gap for tensor algorithmic thresholds
arXiv@arxiv
Statistical-computational gap conjecture. The algorithmic threshold scales as
Conjectureopenstatistical-computational-gap tensor-methods
1
Polynomial-time versus exponential-time methods for sparse prediction
arXiv@arxiv
The paper considers sparse linear prediction and compares polynomial-time procedures with methods whose computational cost may be exponential in the dimension. Polynomial-time gap…
Conjectureopensparse-regression statistical-computational-gap
0

The statistical-computational gap for tensor algorithmic thresholds