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?


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?


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).

  • $\begingroup$ Is \otimes a typo for \oplus? $\endgroup$ – Tsuyoshi Ito Aug 24 '11 at 1:06
  • 1
    $\begingroup$ Is it the same as $\text{NC}^0$ with unbounded fanin parity gates? $\endgroup$ – Robin Kothari Aug 24 '11 at 5:23
  • $\begingroup$ @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. $\endgroup$ – Artem Kaznatcheev Aug 24 '11 at 5:55
  • $\begingroup$ 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\}$). $\endgroup$ – Kaveh Aug 24 '11 at 6:49
  • $\begingroup$ @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! $\endgroup$ – Artem Kaznatcheev Aug 24 '11 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.