12 problems

Gotsman–Linial conjecture. The extremal examples among degree-$d$ polynomial threshold functions for total influence are symmetric polynomials whose signs alternate around the midd…

For a Boolean function $F:\{-1,1\}^{n}\to\{-1,1\}$, define its $i$-th influence by … Its total influence is $\operatorname{Inf}(F)=\sum_{i=1}^{n}\operatorname{Inf}_{i}(F)$. For a p…

Even-$n$, degree-two consequence. For every even $n$, $(n,2)$-HSFs do not exist.

Limiting Gotsman–Linial conjecture. The average sensitivity satisfies

Superweak Gotsman–Linial conjecture. For some function $g$ depending only on $d$,

Asymptotic Gotsman–Linial conjecture. There is an upper bound

Let $S\subseteq\mathbb{R}^d$ be a semi-algebraic set of description complexity $r$, and let $a_1,\dots,a_n\in\mathbb{R}^d$. Define $f:\\{-1,1\\}^n\to\\{0,1\\}$ by letting…

Quadratic PTF influence conjecture. When $k=2$, the bound under discussion should still be

Let a degree-$k$ polynomial threshold function (PTF) be a Boolean function of the form $f(x)=\operatorname{sign}(q(x))$, where $q:\mathbb{R}^n\to\mathbb{R}$ is a real degree-$k$ po…

Let $T(n,d)$ be the number of $n$-variable polynomial threshold functions of degree $d$, and let … Here $\binom{n}{\le d}$ denotes the number of monomials in at most $d$ variables’…

Let $f$ be a Boolean function of $n$ variables, and let $p(x)$ be a real polynomial whose sign represents $f$, so that $f(x)=\operatorname{sgn}(p(x))$. The degree of a polynomial t…

Let $f:\{-1,1\}^n\to\{-1,1\}$ be a degree-$d$ polynomial threshold function, and let $\operatorname{\mathbf{I}}[f]$ denote its total influence. Weak Gotsman–Linial conjecture. For…