UnsolvedMajor
Minimax-Optimal Sparse PCA: Computational–Statistical Gap
Mathematical StatisticsTheoretical Computer Science
Posed by Berthet & Rigollet (formalized) (2013)
Theoretical Computer Science
MSC 68Computational complexity, algorithms, cryptography, quantum computing, formal languages.
4 problems
UnsolvedNotable
Smoothed Complexity of the Simplex Method
Optimization & Variational MethodsTheoretical Computer Science
Posed by Spielman & Teng (implicit) (2004)
UnsolvedMajor
Capacity of the Binary Deletion Channel
Information TheoryTheoretical Computer Science
UnsolvedMajor
Computational Threshold for Tensor PCA
Mathematical StatisticsLearning TheoryTheoretical Computer Science
Posed by Richard & Montanari (2014)