Is there any algorithm for testing if given Boolean function is linear, affine, or bent? What are these properties anyway? Can you describe them using human language, not mathematical formulas?
Thanks for any response, Frank.
Asked
Active
Viewed 196 times
0
-
Yes, there are. Googling will give you dozens of hits -- but you have to be careful about what you mean by "testing", since in the theoretical computer science literature this will typically refer to property testing: "does $f$ satisfy the property, or is it at Hamming distance at least $\varepsilon$ from every function $g$ with the property?" If by "testing" you mean deciding exactly (no gap as in the above), then you cannot have non-trivial algorithms (i.e., you need to query $f$ on all $2^n$ values) – Clement C. Apr 27 '18 at 23:37
-
Can you define what each of these properties mean in mathematical term? – bsbb4 Apr 27 '18 at 23:38
-
Have a look at this, for instance (draft available online): http://www.wisdom.weizmann.ac.il/~oded/pt-intro.html And you may want to use Google, since every single paper or textbook about it defines them. Linear: $f\colon {0,1}^n \to {0,1}$ is linear iff $f(x\oplus y) = f(x)\oplus f(y)$. ($\oplus$ being addition in $\mathbf{F}_2$, and for $x,y\in{0,1}^n$ $x\oplus y$ is that addition, component-wise). – Clement C. Apr 27 '18 at 23:39
-
See also this textbook, also available online as PDF. For instance, a function $f\colon{0,1}^n\to{0,1}$ is bent if all its Fourier coefficients are "very close to uniform". (Definition 26 here) (Note that for Fourier analysis of Boolean function, it is common and convenient to see Boolean functions, equivalently, as $f\colon{-1,1}^n\to{-1,1}$.) – Clement C. Apr 27 '18 at 23:43