10 problems

Let $\binom{[n]}{k}$ denote the family of $k$-element subsets of $[n]=\{1,\ldots,n\}$. For a family $X_n\subseteq\binom{[n]}{k}$, let the local agreement property be the condition…

P-versus-BPP conjecture. Adding randomness does not change what is solvable in polynomial time:

BQP-versus-BPP conjecture. It will not be possible to conclusively prove

Randomness-elimination conjecture. Randomness does not help in graphs of subexponential growth: in this setting, randomized local algorithms should not have an essential advantage…

The deterministic Lovász Local Lemma (LLL) problem asks for a deterministic local algorithm solving instances of the Lovász Local Lemma on graphs, where $n$ denotes the relevant in…

Complete derandomization conjecture. No random bits are necessary for the Legendre-symbol-based construction; equivalently, the construction should satisfy the required restricted…

Let $\textbf{BPP}$ be the class of problems that are polynomial-time computable with a randomized algorithm, and let $\textbf{P}$ be the class of problems that are polynomial-time…

Let $W$ be an explicit variety, and distinguish explicit close-to-defining equations from explicit defining equations as in the source. Explicit equations conjecture. (a) Any expli…

Let $W\subseteq K^m$ be an explicit variety. A strict separating e.s.o.p. is a strict separating homogeneous system of parameters for the coordinate ring $K[W]$; for a weakly expli…

Let $W$ be an explicit variety, and let Noether's Normalization Lemma (NNL) refer to the algorithmic construction of a Noether normalization for $W$. GCT derandomization conjecture…