# Complexity class that captures linear or nearly-linear functions

A particular model I am working with can only compute a function $f: \{0,1\}^n \rightarrow \{0,1\}$ iff $f(x_1,...,x_n)$ is a linear combination (over $\text{GF}(2)$) of the $x_i$'s or has at most a constant amount of non-linearity. What is the complexity class that most closely corresponds to my model?

### Non-linearity

I am not sure if there is a standard definition so let $S,T \subseteq \{1,...,n\}$, and $x_S$ (or, $x_T$) mean the bitstring from only the bits of $x$ whose index is in $S$ (or, $T$). Then we can define a function as $k$-near linear as follows:

$f$ is $0$-near linear if it is linear.

$f$ is $k$-near linear if:

1. $f(x) = g(x_S) \oplus h(x_T)$ and $g$ is $i$-near linear and $h$ is $j$-linear and $i + j = k$.
2. $f(x) = g(x_S) \wedge h(x_T)$ or $f(x) = g(x_S) \vee h(x_T)$ and $g$ is $i$-near linear and $h$ is $j$-near linear and $i + j = k - 1$.

for some $S$, $T$, $g$, and $h$.

If a function is $k$-linear on any input size (where $k$ is a constant) then I say the function has a constant amount of non-linearity. If this is not a standard definition, could you point me in the comments to a standard definition? Is my definition obviously equivalent to some other standard definition?

### Question

What is the complexity class associated with functions that are $k$-near linear? And how does it compare to other popular complexity classes?

I can obviously simulate $\mathsf{NC}_0$. However, I can also compute parity, and can't compute the $\text{OR}$ function on $n$ bits, and so the complexity class is incomparable to $AC_0$. I have also heard of width-$2$ OBDDs as 'the next step' after linear, however the characterizations of approximating width-$2$ OBDDs I have seen allow for a logarithmic amount of non-linearity (as far as I can tell).

• Is \otimes a typo for \oplus? – Tsuyoshi Ito Aug 24 '11 at 1:06
• Is it the same as $\text{NC}^0$ with unbounded fanin parity gates? – Robin Kothari Aug 24 '11 at 5:23
• @Robin yeah, as far as I can tell they would be equivalent. Are there results known for $\mathsf{NC}^0$ with unbounded fanin parity gates? It doesn't come up in the complexity zoo, at least not under that name. – Artem Kaznatcheev Aug 24 '11 at 5:55
• I think your definition may need modification but essentially it will correspond to polynomials of degree k (using $\{1,-1\}$ in place of $\{0,1\}$). – Kaveh Aug 24 '11 at 6:49
• @Kaven that would capture the goal of partial non-linearity very nicely... but I am a little doubtful that would be equivalent to my definition, especially if the polynomials are $\mathbb{R^n} \rightarrow \mathbb{R}$, but I will think about it more, thank you! – Artem Kaznatcheev Aug 24 '11 at 7:12