Return to Question

Let $\mathbb{F}$ be the field of size 2. Say I have functions $p_1,\ldots,p_m : \mathbb{F}^n \to \mathbb{F}$ each with high degree $\approx n$ as (multilinear) polynomials, and another function $s : \mathbb{F}^m \to \mathbb{F}$ also with high degree $\approx m$. Are there general properties of $s$ and the $p_i$ that characterize when $f(x) := s(p_1(x),\ldots,p_m(x)) : \mathbb{F}^n \to \mathbb{F}$ can have very low degree, i.e. degree $\ll n$?

It's easy to come up with toy examples -- I'm wondering if there are any general statements one can make. E.g., some relationship among the $p_i$ that says that no choice of $s$ can reduce the degree too much, or a proof that for any set of $p_i$ there is some $s$ that reduces the degree by a lot, etc.

Let $\mathbb{F}$ be the field of size 2. For a function $f : \mathbb{F}^n \to \mathbb{F}$, let $d(f)$ be the smallest integer such that there exists a degree-$d(f)$, $n$-variate, multilinear polynomial that induces $f$ on $\mathbb{F}^n$.

Say I have functions $p_1,\ldots,p_m : \mathbb{F}^n \to \mathbb{F}$ each with high degree $d(p_i) \approx n$, and another function $s : \mathbb{F}^m \to \mathbb{F}$ also with high degree $d(s) \approx m$. Let $f : \mathbb{F}^n \to \mathbb{F}$ be the composition $f(x) := s(p_1(x),\ldots,p_n(x))$. Are there general properties of $s$ and the $p_i$ that characterize when $f$ can have very low degree, i.e. $d(f) \ll n$?

It's easy to come up with toy examples -- I'm wondering if there are any general statements one can make. E.g., some relationship among the $p_i$ that says that no choice of $s$ can reduce the degree too much, or a proof that for any set of $p_i$ there is some $s$ that reduces the degree by a lot, etc.

Let $\mathbb{F}$ be the field of size 2. Say I have polynomials $p_1,\ldots,p_m : \mathbb{F}^n \to \mathbb{F}$ with high degree $\approx n$, and another polynomial $s : \mathbb{F}^m \to \mathbb{F}$ with high degree $\approx m$. Are there general properties of $s$ and the $p_i$ that characterize when $f(x) := s(p_1(x),\ldots,p_m(x)) : \mathbb{F}^n \to \mathbb{F}$ can have very low degree, i.e. degree $\ll n$?

It's easy to come up with toy examples -- I'm wondering if there are any general statements one can make. E.g., some relationship among the $p_i$ that says that no choice of $s$ can reduce the degree too much, or a proof that for any set of $p_i$ there is some $s$ that reduces the degree by a lot, etc.

Let $\mathbb{F}$ be the field of size 2. Say I have functions $p_1,\ldots,p_m : \mathbb{F}^n \to \mathbb{F}$ each with high degree $\approx n$ as (multilinear) polynomials, and another function $s : \mathbb{F}^m \to \mathbb{F}$ also with high degree $\approx m$. Are there general properties of $s$ and the $p_i$ that characterize when $f(x) := s(p_1(x),\ldots,p_m(x)) : \mathbb{F}^n \to \mathbb{F}$ can have very low degree, i.e. degree $\ll n$?

It's easy to come up with toy examples -- I'm wondering if there are any general statements one can make. E.g., some relationship among the $p_i$ that says that no choice of $s$ can reduce the degree too much, or a proof that for any set of $p_i$ there is some $s$ that reduces the degree by a lot, etc.