On the structure and numbers of higher order correlation-immune functions
Yuriy Valerievich Tarannikov · 2002
It is proved by means of a Ramsey-like technique that for each positive integer k there exists a minimal nonnegative integer p'(k) that any n-k th order correlation-immune function of n binary input variables, f/spl ne/const, depends nonlinearly on at most p'(k) inputs. It is proved that the number of n-k th order correlation-immune functions of n binary input variables, k=const, n/spl rarr//spl infin/, is polynomial. For k=1, 2, 3 the exact formulas for the numbers of such functions are obtained.