Linearity tests are randomized algorithms which have oracle access to the truth table of some function $f$,
which are supposed to distinguish between linear functions and functions which are far from linear. Linearity tests were first introduced by Blum, Luby and Rubenfeld in \cite{BLR93}, and were later used in the ... more >>>