6 problems

Let $X$ be an $n\times n$ matrix of indeterminates, and let $I_n$ be the ideal generated by the $\tfrac{n}{2}\times\tfrac{n}{2}$ minors of $X$. For a nonzero polynomial $f\in I_n$,…

Odd Alternating Cycle Conjecture. For every field $\mathbb{F}$ there exist $\varepsilon>0$ and an odd integer $\ell$ such that every $n$-vertex directed graph $G$ with

Barrington–Straubing–Thérien conjecture. There exists $q>0$ such that $C_n$ has size

For a Boolean function $f$, define its total influence by … A Boolean function $g$ $\epsilon$-approximates $f$ when $\mathbb E(f-g)^2\le\epsilon$. Low-influence approximation conje…

Let $f$ be a Boolean function, and let $M$ and $D$ denote the size and depth of a threshold circuit representing it. A circuit is monotone threshold when its threshold gates have n…

Grigoriev–Koshevoy's conjecture. The tropical semiring complexity of $\operatorname{Trop}(s_{\lambda/\mu})$ is at least exponential.