11 problems

VFPT versus VW[1] conjecture. There exists a weft-$1$-definable parameterized p-family that is not in $\mathrm{VFPT}$.

Valiant's conjecture. There exists a Boolean-definable sequence $(f_d)_{d\in\mathbb{N}}$ with

Valiant's conjecture. Valiant's conjecture for $R$ is

Let $f\in\mathbb{Z}[x_1,\ldots,x_n]$ be nonzero. Let $\operatorname{rad}(f)$ denote the product of the distinct irreducible factors of $f$, and let $L(h)$ denote the size of the sm…

Factor Conjecture. One has

Let $f$ be a univariate polynomial whose arithmetic circuit complexity is bounded by $s$. Shub–Smale's $\tau$-conjecture. The number of integer zeros of $f$ is bounded by a polynom…

Let $f$ be a univariate polynomial of the form … where each $f_{ij}$ is $k$-sparse. Koiran's real $\tau$-conjecture. The number of real zeros of $f$ is bounded by a polynomial in…

Beecken–Michałek–Saxena bounded-rank conjecture. The algebraic rank of such circuits is $O_k(\log d)$.

Let $a_0=2-1$ and, for $n\geq 0$, let … Consider formula encodings whose gates are restricted to \{+,\times,\text{^}\} and whose inputs are restricted to $\{-1,1\}$. The asymptot…

Let $f$ be a single-variable polynomial computed by an algebraic circuit, and let the size of the circuit be measured by its circuit size. The $\tau$-conjecture. The number of inte…

Valiant's weakly skew conjecture.