<p>A particular model I am working with can only compute a function <span class="math-container">$f: \{0,1\}^n \rightarrow \{0,1\}$</span> iff <span class="math-container">$f(x_1,...,x_n)$</span> is a linear combination (over <span class="math-container">$\text{GF}(2)$</span>) of the <span class="math-container">$x_i$</span>'s or has at most a constant amount of non-linearity. What is the complexity class that most closely corresponds to my model?</p>
<h3>Non-linearity</h3>
<p>I am not sure if there is a standard definition so let <span class="math-container">$S,T \subseteq \{1,...,n\}$</span>, and <span class="math-container">$x_S$</span> (or, <span class="math-container">$x_T$</span>) mean the bitstring from only the bits of <span class="math-container">$x$</span> whose index is in <span class="math-container">$S$</span> (or, <span class="math-container">$T$</span>). Then we can define a function as <span class="math-container">$k$</span>-near linear as follows:</p>
<blockquote>
<p><span class="math-container">$f$</span> is <span class="math-container">$0$</span>-near linear if it is linear.</p>
<p><span class="math-container">$f$</span> is <span class="math-container">$k$</span>-near linear if:</p>
<ol>
<li><span class="math-container">$f(x) = g(x_S) \oplus h(x_T)$</span>  and <span class="math-container">$g$</span> is <span class="math-container">$i$</span>-near linear and <span class="math-container">$h$</span> is <span class="math-container">$j$</span>-linear and <span class="math-container">$i + j = k$</span>.</li>
<li><span class="math-container">$f(x)  = g(x_S) \wedge h(x_T)$</span> or <span class="math-container">$f(x)  = g(x_S) \vee h(x_T)$</span> and <span class="math-container">$g$</span> is <span class="math-container">$i$</span>-near linear and <span class="math-container">$h$</span> is <span class="math-container">$j$</span>-near linear and <span class="math-container">$i + j = k - 1$</span>.</li>
</ol>
<p>for some <span class="math-container">$S$</span>, <span class="math-container">$T$</span>, <span class="math-container">$g$</span>, and <span class="math-container">$h$</span>.</p>
</blockquote>
<p>If a function is <span class="math-container">$k$</span>-linear on any input size (where <span class="math-container">$k$</span> 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?</p>
<h3>Question</h3>
<blockquote>
<p>What is the complexity class associated with functions that are <span class="math-container">$k$</span>-near linear? And how does it compare to other popular complexity classes?</p>
</blockquote>
<p>I can obviously simulate <span class="math-container">$\mathsf{NC}_0$</span>. However, I can also compute parity, and can't compute the <span class="math-container">$\text{OR}$</span> function on <span class="math-container">$n$</span> bits, and so the complexity class is incomparable to <span class="math-container">$AC_0$</span>. I have also heard of width-<span class="math-container">$2$</span> OBDDs as 'the next step' after linear, however the characterizations of approximating width-<span class="math-container">$2$</span> OBDDs I have seen allow for a logarithmic amount of non-linearity (as far as I can tell).</p>

CC BY-SA 3.0
2011-08-24T01:06:52.930Z
Is \otimes a typo for \oplus?
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-24T05:23:28.583Z
Is it the same as $\text{NC}^0$ with unbounded fanin parity gates?
Robin Kothari
CC BY-SA 3.0
2011-08-24T05:55:46.480Z
@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
CC BY-SA 3.0
2011-08-24T06:49:43.893Z
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
CC BY-SA 3.0
2011-08-24T07:12:19.863Z
@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
CC BY-SA 3.0
2011-08-24T07:17:36.520Z
@Robin I might have jumped the gun a bit of the equivalence of $\mathsf{NC}^0$ with unbounded fan-in parity gates and my model... I am a little worried about things like doing lots (non-constant) number of ANDs/ORs in the first level and then combining their results with an XOR in the second level, but I will think about it more.
Artem Kaznatcheev
<cc.complexity-theory><complexity-classes>
Complexity class that captures linear or nearly-linear functions
Artem Kaznatcheev
# Complexity class that captures linear or nearly-linear functions

(Asked by: username_0 on 2011-08-24)

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

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: Is \otimes a typo for \oplus?  
> **username_2**: Is it the same as $\text{NC}^0$ with unbounded fanin parity gates?  
> **username_0**: @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.  
> **username_3**: 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\}$).  
> **username_0**: @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!  
> **username_0**: @Robin I might have jumped the gun a bit of the equivalence of $\mathsf{NC}^0$ with unbounded fan-in parity gates and my model... I am a little worried about things like doing lots (non-constant) number of ANDs/ORs in the first level and then combining their results with an XOR in the second level, but I will think about it more.  

---

## 0 answers

