Unsolved Problems

Conjecture If $X_1, \dotsc, X_n \geq 0$ are independent random variables with $\mathbb{E}[X_i] \leq \mu$, then $$\mathrm{Pr} \left( \sum X_i - \mathbb...

Conjecture The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{...

Question What is the complexity of the following problem? Given $a_1,\dots,a_n; k$, determine whether or not $\sum_i \sqrt{a_i} \leq k.$...

Problem Can $O(n)$-size circuits compute the function $f$ on $\{0,1,2\}^*$ defined inductively by $f(\lambda) = \lambda$, $f(0x) = 0f(x)$, $f(1x) = 1f...