Theoretical Computer Science

Minimax-Optimal Sparse PCA: Computational–Statistical Gap

Posed by Berthet & Rigollet (formalized) (2013)

AdaBoost Always Cycles? (Global Dynamics Conjecture)

Posed by Rudin, Daubechies, and Schapire (2004)

Smoothed Complexity of the Simplex Method

Posed by Spielman & Teng (implicit) (2004)

Capacity of the Binary Deletion Channel

Computational Threshold for Tensor PCA

Posed by Richard & Montanari (2014)

Fixed-Parameter Tractability of Zonotope Problems

Posed by Vincent Froese et al. (2025)

Optimal Instance-Dependent Sample Complexity for finding Nash Equilibrium in Two Player Zero-Sum Matrix games

Posed by Arnab Maiti (2025)

What is the Complexity of Joint Differential Privacy in Linear Contextual Bandits?

Posed by Achraf Azize et al. (2024)

Optimal Rates for Stochastic Decision-Theoretic Online Learning Under Differentially Privacy

Posed by Bingshan Hu et al. (2024)

The Sample Complexity of Multi-Distribution Learning for VC Classes

Posed by Pranjal Awasthi et al. (2023)

Properly learning decision trees in polynomial time?

Posed by Guy Blanc et al. (2022)

Running time complexity of accelerated $\ell_1$-regularized PageRank

Posed by Kimon Fountoulakis et al. (2022)

Do you pay for Privacy in Online learning?

Posed by Amartya Sanyal et al. (2022)

Better Differentially Private Learning Algorithms with Margin Guarantees

Posed by Raef Bassily et al. (2022)

Information Complexity of VC Learning

Posed by Thomas Steinke et al. (2020)

Is Margin Sufficient for Non-Interactive Private Distributed Learning?

Posed by Amit Daniely et al. (2019)

The Oracle Complexity of Convex Optimization with Limited Memory

Posed by Blake Woodworth et al. (2019)

The Dependence of Sample Complexity Lower Bounds on Planning Horizon

Posed by Nan Jiang et al. (2018)